USERGUIDE.md

Eisenstein

This is a detailed guide on what methods are available in this package, and how to use them.

Eisenstein circle packings

We represent circle packings by Eisenstein quadruples, i.e. a primitive integral vector $(a, b, c, d)$ with $a+b+c+d>0$ and $a^2+b^2+c^2+d^2=2(a+c)(b+d)$. We require it to be in standard position, i.e. $a\equiv b\pmod{2}$ and $c\equiv d\pmod{2}$. If it is the reduced quadruple, we typically reorder so that $a\leq 0$. It should be stored as a t_VECSMALL, but t_VEC/t_COL (with t_INT entries) is also acceptable. Be aware that built-in methods generally return t_VECSMALLs, even if you input a t_VEC/t_COL.

In general, methods for Eisenstein circle packings are of the form eis_METHOD.

The method eis_makeall(a) returns all primitive quadruples containing curvature a. We make a the first curvature, put it in standard position, and ensure it is 1-reduced: swapping the curvatures in index 2/3/4 do not decrease the quadruple. Possible Eisenstein quadruples be checked with eis_check(v), which validates the input.

? v = eis_makeall(-3)
%1 = [Vecsmall([-3, 17, 20, 4]), Vecsmall([-3, 5, 14, 10])]
? eis_check(v[2])
%2 = 1
? eis_check([-3, 17, 20, 2]) /*Does not satisfy the Eisenstein equation*/
%3 = 0

We can execute circle swaps and reduce the quadruple with eis_swap and eis_reduce. Note that these always return t_VECSMALLs, as this is the preferred way to work with the quadruples.

? v = eis_swap(Vecsmall([-4, 18, 19, 7]), [1, 2, 1, 3, 4, 2])
%1 = Vecsmall([216, 806, 251, 927])
? eis_swap(v, 2)
%2 = Vecsmall([216, 128, 251, 927])
? eis_reduce(v)
%3 = Vecsmall([-4, 18, 19, 7])
? eis_reduce(v, 2)
%4 = [Vecsmall([-4, 12, 19, 7]), Vecsmall([2, 4, 1, 3, 2, 1, 2])]
? eis_reduce(Vecsmall([9, 5, -2, 4]), 0)
%5 = Vecsmall(9, 5, -2, 4)
? eis_reduce(Vecsmall([9, 5, -2, 4]), 1)
%6 = Vecsmall(-2, 4, 9, 5)

Passing between binary quadratic forms and Eisenstein quadruples is accomplished with eis_quadrupletoqf and eis_qftoquadruple. We format (primitive positive semidefinite first-odd) binary quadratic forms as length 3 t_VECSs. We do not use the built-in t_QFB data type, as we are working with a different equivalence to ususal ($\Gamma_0^{\text{PGL}}(2)$ equivalence). We provide an additional reduction method for these quadratic forms.

? q = eis_quadrupletoqf(Vecsmall([-7, 33, 40, 10]), 2)
%1 = [73, 23, 13]
? eis_qftoquadruple(q, 33, 4) /*Remake the quadruple, but put it in the 4th position.*/
%2 = Vecsmall([40, 10, -7, 33])
? eis_qfreduce([247, 905, 829])
%3 = [1, 1, 7]

The type of a quadruple determines the modulo 4 behaviour of the curvatures in the packing. There are two types, $[3, 1]$ and $[3, 3]$, representing ${0, 1, 2}\pmod{4}$ and ${0, 2, 3}\pmod{4}$ respectively.

? eis_type(Vecsmall([-4, 28, 33, 5]))
%1 = [3, 1]
? eis_type(Vecsmall([-4, 12, 19, 7]))
%2 = [3, 3]

The reciprocity obstructions are determined by the $\chi_2$ value. We output these values for the odd and even index circles. If they type is [3, 1], those are the same, else they are negatives of each other.

? eis_chi2(Vecsmall([-2, 8, 11, 3]))
%1 = [1, -1]
? eis_chi2(Vecsmall([-2, 4, 9, 5]))
%2 = [1, 1]
? eis_type(Vecsmall([-2, 4, 9, 5]), 1)
%3 = [3, 1, [1, 1]]

To study the curvatures/quadruples that appear/are missing, use the methods eis_frequencies, eis_missing, eis_quadruples, and eis_sporadic.

? eis_missing(Vecsmall([-3, 5, 14, 10]), [10^5, 10^5+1000])
%1 = [[Vecsmall([100352]), Vecsmall([100489]), Vecsmall([100398, 100854]), Vecsmall([])], [Vecsmall([100352, 100872]), Vecsmall([100489]), Vecsmall([]), Vecsmall([])]]
? eis_quadruples(Vecsmall([-6, 14, 23, 15]), 30)
%2 = [Vecsmall([-6, 14, 23, 15]), Vecsmall([-6, 20, 23, 15]), Vecsmall([-6, 20, 23, 19]), Vecsmall([-6, 14, 23, 19])]
? fr = eis_frequencies(Vecsmall([-5, 11, 20, 12]), [10^5, 10^5+20])
%3 = [[Vecsmall([3, 4, 8, 7, 7, 5]), 0, Vecsmall([1, 3, 4, 2, 1]), Vecsmall([4, 4, 6, 7, 4])], [Vecsmall([7, 1, 11, 5, 4, 5]), 0, Vecsmall([6, 1, 4, 5, 3]), Vecsmall([6, 4, 5, 7, 8])]]
? vector(21, i, eis_frequencies_search([10^5, 10^5+20], fr, 10^5+i-1))
%4 = [[3, 7], [0, 0], [1, 6], [4, 6], [4, 1], [0, 0], [3, 1], [4, 4], [8, 11], [0, 0], [4, 4], [6, 5], [7, 5], [0, 0], [2, 5], [7, 7], [7, 4], [0, 0], [1, 3], [4, 8], [5, 5]]
? vector(21, i, eis_frequencies_search([10^5, 10^5+20], fr[1], 10^5+i-1))
%5 = [3, 0, 1, 4, 4, 0, 3, 4, 8, 0, 4, 6, 7, 0, 2, 7, 7, 0, 1, 4, 5]
? eis_sporadic(Vecsmall([-3, 5, 14, 10]), [10^5, 10^5+1000])
%6 = [[Vecsmall([]), Vecsmall([]), Vecsmall([100398, 100854]), Vecsmall([])], [Vecsmall([100872]), Vecsmall([]), Vecsmall([]), Vecsmall([])]]

As seen above, the method eis_frequencies_search is a convenient way to process the output of eis_frequencies.

Visualization

Circles in an Eisenstein packing are stored as an integral quadruple $(s, t, x, z)$ (see below, the Eisenstein Schmidt arrangement section). These quadruples can be generated with eis_circles, and compiled into a pdf picture (using LaTeX and tikz) using eis_display. Automatic compiling is recommended, see the "Optional Packages" section of the README for more. Note that eis_display has many options for the output, be sure to check the help with ?eis_display.

? c = eis_circles(Vecsmall([-13, 27, 54, 32]), 60)
%1 = [[-13, -12, -20, 3], [27, 26, 42, -7], [54, 50, 84, -11], [32, 28, 48, -7], [55, 50, 86, -9], [50, 48, 80, -9]]
? t = eis_display(c, "pic1") /*Default options*/
%2 = ["pic1", 1, 0]
? f(x) = {return(min(gcd(x[1], x[2]), 2));}; /*Colour based on if the curvature and co-curvature are coprime*/
? t1 = eis_display(c, "pic2", , f)
%4 = ["pic2", 1, 0]

You may wish to edit the raw LaTeX file of the circle packing and recompile. The corresponding file above will be found in ./images/build/pic1_build.tex. Once you edit it, you can use the output of eis_display to recompile: tex_recompile(t).

The file makepictures.gp also includes some methods to collect circle packing pictures into one file, draw the strip packing out more, and draw parts of the Eisenstein Schmidt arrangement. See the inline help in the file for how to use it. For example, to make a nice strip packing picture, you can do:

? \r makepictures
? c = strippack_cut(200, 3, 0.2, 4.8);
? eis_display(c, "strip");

To draw part of the Eisenpint Schmidt arrangement, you can do:

? \r makepictures
? c = schmidt_circles_box(20, 1, 6, 4);
? eis_display(c, "eisenpint20", 0);

Eisenstein integers

Let $\omega=\frac{1+\sqrt{-3}}{2}$, so that $\omega^2-\omega+1=0$. We store the Eisenstein integer $a+b\omega$ (where $a,b\in\mathbb{Z}$) as a t_COL, [a, b]~. We supply a few methods to compute basic operations with Eisenstein integers.

In general, methods for Eisenstein integers are of the form eisMETHOD (no underscore).

? a = [34, -41]~; b = [-43, 29]~;
? eismul(a, b)
%2 = [-273, 1560]~
? eisnorm(a)
%3 = 1443
? eisconj(a)
%4 = [-7, 41]
? eisgcd(a, b)
%5 = [1, -11]~
? eisbezout(a, b)
%6 = [[2, -2]~, [1, -2]~, [1, -11]~]
? eismul(a, [2, -2]~) + eismul(b, [1, -2]~)
%7 = [1, -11]~
? eisdivalg([2, 11]~, [5, -3]~)
%8 = [[-2, 3]~, [3, -1]~]
? eismul([-2, 3]~, [5, -3]~) + [3, -1]~
%9 = [2, 11]~
? eisunits()
%10 = [[1, 0]~, [-1, 0]~, [0, 1]~, [0, -1]~, [1, -1]~, [-1, 1]~]

We have a few methods to work with $2\times 2$ matrices of Eisenstein integers

? M = [[1, 2]~, [3,- 2]~; [4, 5]~, [2, 17]~]; N = [[-3, 0]~, [2, 5]~; [-3, -4]~, [1, 2]~];
? eis_matdet(M)
%2 = [-54, 58]~
? print(eis_matmul(M, N))
%3 = [[-20, -4]~, [-1, 19]~; [50, -142]~, [-49, 110]~]
? T = eis_matfrombotrow([4, 5]~, [2, 11]~ ); print(T);
%4 = [[3, -1]~, [4, 0]~; [4, 5]~, [2, 11]~]
? eis_matdet(T)
%5 = [1, 0]~
?  eis_matfrombotrow([1, 2]~, [1, 2]~)
%6 = 0

Eisenstein Schmidt arrangement

For each $M\in\text{PSL}(2, \mathbb{Z}[\omega])$, the image $M(\widehat{\mathbb{R}})$ is a circle. We represent it by its reduced quadruple, a quadruple of integers $(s, t, x, z)$, where $-3st+x^2-xz+z^2=1$ and $x+z\equiv 2\pmod{3}$. This represents a circle with curvature $s\sqrt{3}$, co-curvature $t\sqrt{3}$, and curvature-centre $\frac{x\sqrt{3}+(x-2z)i}{2}$. The circle/matrix also are equipped with a coset, which describles the reduction of the circle modulo 2. There are 10 cosets, and they determine the tangency behaviour of different circles.

Here are the basic methods:

? M = [[-1, 4]~, [-3, 5]~; [1, 2]~, [0, 3]~];
? c = eis_tocircle(M)
%2 = [3, 7, 8, 0]
? eis_coset(c)
%3 = 5
? eis_coset(M) /*Allows for c or M or [M, c] input*/
%4 = 5
? eis_location(c) /*Allows for c or M or [M, c] input*/
%5 = [0, 0]~
? c2 = eis_trans(c, [2, 3]~) /*Allows for c or M or [M, c] input*/
%6 = [3, 104, 29, -3]
? eis_location(c2)
%7 = [2, 3]~
?  eis_coset(c2)
%8 = 6
? M1 = eis_tomat(c2) /*We can also go backwards from the reduced quadruple to a matrix*/
%9 =
[[-7, 3]~ [-9, -11]~]
[[-1, 1]~   [-3, 0]~]
? eis_tocircle(M1)
%10 = [3, 104, 29, -3]
? eis_chi2([9, 8, 16, 3]) /*Also allows for circle input (as long as it is coset 0/4)*/
%11 = 1

We also allow such quadruples where $x+z\equiv 1\pmod{3}$, which correspond to the opposite orientation of one of the above circles. The eis_(coset/location/trans) methods also allow input of M or [M, c], where c=eis_tomat(M). In the last case, the output retains the same format.

If a circle begins in coset 0/4, we ensure that the matrix output is in the Eisenpint group.

To compute the inversive distance between circles (necessarily an integer or half-integer),

? eis_invdist([3, 7, 8, 0], [3, 7, 8, 0])
%1 = 1
? eis_invdist([-6, -5, -6, 5], [-6, 0, -1, 0])
%2 = -73/2

Starting with an Eisenstein quadruple, we can find where a component circle located in the En-Schmidt arrangement (a representative of the equivalence class, which is either the real line, or whose centre lies in the rectangle from 0 - 1 - 1+sqrt(3)/2i - sqrt(3)/2i. The equivalence classes lie in the unoriented En-Schmidt arrangement, hence the curvature may negate.

? eis_toschmidt(Vecsmall([-5, 19, 24, 8]), 2)
%1 = [[[-1, -2]~, [8, -4]~; [-2, -1]~, [7, -6]~], [19, 20, 36, 5]]

We also provide methods to pass between these representations and quadratic forms, with eis_toqf and the previously mentioned eis_to(mat/circle). If we start with a quadratic form, the circle is guaranteed to be in coset 0/4, and the matrix in the Eisenpint group.

? q1 = eis_toqf([19, 20, 36, 5])
%1 = [49, 17, 7]
? q2 = eis_toqf([[-1, -2]~, [8, -4]~; [-2, -1]~, [7, -6]~])
%2 = [43, -11, 7]
? eis_qfreduce(q1) == eis_qfreduce(q2)
%3 = 1
? c1 = eis_tocircle(q1) /*Outputs an equivalent circle, not necessarily equal!*/
%4 = [-19, -20, -36, -31]
? M1 = eis_tomat(q2) /*Outputs an equivalent matrix, not necessarily equal!*/
%5 =
[[3, -2]~ [-4, -4]~]
[[3, -1]~ [-1, -6]~]
? eis_qfreduce(eis_toqf(M1)) == eis_qfreduce(eis_toqf(c1))
%6 = 1

We can find all the circles in the full Eisenstein Schmidt arrangement of curvature N whose centre lies inside the fundamental polygon (parallelogram with vertices of $0,1,1+\omega,\omega$) using eis_schmidtfund(N). The set of all such circles is then obtained via all translations by $\mathbb{Z}[\omega]$, which can be practically accomplished using eis_circletrans. Note that replacing $N$ with $-N$ will produce a different result, and if you want all unoriented circles of curvature $\pm N$, you need to combine both outputs.

? eis_schmidtfund(4)
%1 = [[4, 4, 8, 3], [4, 2, 5, 0], [4, 1, 4, 1], [4, 10, 11, 0], [4, 1, 3, -1], [4, 4, 5, -3]]
? eis_schmidtfund(-4)
%2 = [[-4, -3, -4, 3], [-4, 0, -1, 0], [-4, -6, -8, 1], [-4, -4, -7, 0], [-4, -6, -9, -1], [-4, -3, -7, -3]]

We can also work with the 10 cosets of circles. The function eis_schmidtselect allows you to collect a range of curvatures, and output all circles in a range of cosets whose circle centres lie inside the parallelogram with vertices of $0,2,2+2\omega,2\omega$. To generate the entire packing, combine with translations by $\mathbb{Z}[2\omega]$.

? eis_schmidtselect([1, 2], [0, 4])
%1 = [[1, 4, 4, 1], [-1, -2, -2, 1], [2, 2, 4, 1], [2, 8, 8, 3], [-2, -6, -4, 3], [-2, -12, -8, 1]]

Additional methods

We use qfblift internally, but leave public access as it is an independantly useful function. Given a primitive integral t_QFB q of discriminant Dn^2, we find a reduced primitive integral q' of discriminant D and a primitive integral matrix M of determinant |n| for which $M\circ q' = q$.

? qfblift(Qfb(71, 139, 72), 7)
%1 = [Qfb(2, -1, 3), [-4, -5; 3, 2]]
? 2*(-4*x-5*y)^2-(-4*x-5*y)*(3*x+2*y)+3*(3*x+2*y)^2
%2 = 71*x^2 + 139*y*x + 72*y^2

We include some linear regression methods, which are useful for data analysis. Ordinary least squares regression is captured in OLS, and we have two useful shortcuts for common situations. If we want to regress on $y=kx$ only, we can use OLS_nointercept, and if we want to regress on $y=a+bx$, we can use OLS_single.

? X = [1,1,1,1;1,2,3,4;1,4,9,16];
? y = [3,7,13,21]~;
? OLS(X, y) /*Returns [params, rsq]*/
%3 = [[1, 1, 1]~, 1]
? rsquared(X, y, [1, 1, 1]~)
%4 = 1
? rsquared(X, y, [1, 1, 1/2]~)
%5 = 191/368
? y2 = [3, 6, 14, 20]~;
? OLS(X, y2)
%7 = [[-1/4, 43/20, 3/4]~, 3526/3575]
? OLS_nointercept([1, 2, 3, 4], [2, 4, 6, 8]) /*Returns [k, rsq]*/
%8 = [2, 1]
? OLS_single([1, 2, 3, 4], [3, 5, 7, 9]) /*Returns [[a, b]~, rsq]*/
%9 = [[1, 2]~, 1]

Finally, the file strongapprox.gp includes naive methods to compute the sizes of SL(2, Z[omega]) (mod N), as well as the group E'' (mod N), which are used to verify the exact bad modulus in strong approximation.