Integral points in rational polygons: a numerical semigroup approach

INTEGRAL POINTS IN RATIONAL POLYGONS: A NUMERICAL SEMIGROUP APPROACH GUADALUPE M´ ARQUEZ–CAMPOS, JORGE L. RAM´ IREZ–ALFONS´ IN, AND JOS´ E M. TORNERO Abstract. In this paper we use an elementary approach by using numerical semigroups (specifically, those with two generators) to give a formula for the number of integral points inside a right–angled triangle with rational vertices. This is the basic case for computing the number of integral points inside a rational (not necessarily convex) polygon. 1. Introduction: A little bit of history In recent times, impressive advances in computational combinatorics and the ever–increasing amount of applications to other branches of mathematics have made lattice–point counting a fruitful and dynamic research field. The problem of computing the set of integral points inside plane bodies has a long history. We will see how to reduce this problem to an interated application of Theorem 2. A milestone in this story is Pick’s Theorem [16], from the late years of the 19th century. Theorem 1. Let Sbe a polygon such that all of its vertices are integral, and int(S) and ∂S are, respectively, its interior and its boundary, let A(S)be the area of S, I(S) = # Z2∩int(S), B(S) = # Z2∩∂S. Then A(S) = I(S) + B(S) 2−1. More specifically, the question of counting lattice (in particular integral1) points inside a right triangle has a long and interesting story. As early as 1922 Hardy and Littlewood [9] studied the problem of right triangles defined by the coordinate axes and a hypotenuse with irrational slope. In the following years, the interest for the subject did not decline. For instance, in [7] Ehrhart introduced the so–called Ehrhart quasi–polynomials, an almost ubiquous tool nowadays. In [15] Mordell established a connection between lattice points problems (for the tetrahedron) and Dedekind sums while in [17] Pommersheim derived a more genaral formula by using techniques from algebraic geometry, see also [21]. Date: June 23, 2016. 2010 Mathematics Subject Classification. Primary: 11H06, 11P21; Secondary: 20M13, 11–04. Key words and phrases. Lattice points, numerical semigroups, geometry of numbers. First and third authors were partially supported by the grant FQM–218 and P12–FQM–2696 (FEDER and FSE). The second author was supported by ANR TEOMATRO grant ANR-10- BLAN 0207 and grant ECOS-Nord M13M01. 1Throughout this paper we will call a point P∈R2integral if its coordinates lie in Z2, and similarly Pwill be called rational if P∈Q2. 1 2 G. M ´ ARQUEZ–CAMPOS, J.L. RAM´ IREZ–ALFONS´ IN, AND J.M. TORNERO A very good and comprehensive introduction to the subject, with a good share of deep results is Beck and Robins book [4] where, in particular, the reader can find a formula, due the same authors [3], to compute the number of integral points inside a right triangle. Their approach is quite different from ours, they came out with a formula that uses either n–th primitive roots of unity or Fourier–Dedekind sums. The latter allowed them to give an efficient algorithm to calculate the number of integral points inside a right triangle since Dedekind sums with 2 variables can be computed in polynomial time. In this regard, we mention a polynomial time algorithm, due to Barnikov [1, 2] (that has significally influenced the field) that enumerates the lattice points of rational polytopes in fixed dimension. Let us finally mention an interesting generalization of our problem. Let us call a right tetrahedron the convex set of Rn ≥0limited by the coordinate hyperplanes and a hyperplane a1x1+... +anxn= 1, with ai∈R. The question of counting (more precisely, bounding) the number of points in n–dimensional right tetrahedra has been a subject of study of S.S.T. Yau and some of his collaborators [11, 12, 13, 22, 23, 24, 25], a research that produced the so–called GLY conjecture (named after its creators, A. Granville, K.P. Lin and S.S.T. Yau). This conjecture gives a lower estimate for the number of integral points in an n–dimensional right tetrahedron in terms of its vertex coordinates (the weak estimate) and in terms of these coordinates and the Stirling numbers (the strong estimate). The weak version was proved by Yau and Zhang [26]. Asfor the strong version is concerned, the authors claim in the same paper that it has been checked computationally up to n= 10. The fact is that the conjecture might be checked for a particular n, but the state–of–the–art has not changed since. According to the authors, the case n= 10 took weeks to be completed. This result came handy to the first and third author in [14]. Please note that the GLY conjecture only applies to n≥3. The main result of this paper is concerned with the following situation. Theorem 2. Let a < b be coprime integers, c∈Z. Consider the following set: T=(y1, y2)∈Z2 ≥0|ay1+by2≤c. Then #T=−ab 2k2+a+b+ 1 + 2c 2k+ ⌊c−kab b⌋ X i=0 c−kab −ib a+ 1 where k=⌊c/(ab)⌋. Equivalently, by using the Euclidean division c=q·ab +r, the above formula can be expressed in the following alternative way #T=−ab 2q2+a+b+ 1 + 2c 2q+ ⌊r/b⌋ X i=0 r−ib a+ 1. Our technique to prove this result is based essentially in numerical semigroup invariants (the relationship between semigroups and lattice points problems has already been remarked in [20]). Although the above formula is not polynomial in the input size (since the sum has aterms in the worse case), we think that this elementary approach (avoiding Fourier analysis) might suggest a number of follow–up questions, which would be fruitful to investigate. Two such questions are shown as applications of the main result in the last section. The first one will be computing the number of integral points inside a INTEGRAL POINTS IN RATIONAL POLYGONS 3 polygon with rational vertices. The second will explore a possible application to a well–known problem in numerical semigroups: the computation of the denumerant. 2. An interlude on numerical semigroups This paper relies on numerical semigroups as a fundamental tool. A numerical semigroup is a very special kind of semigroup that can be thought of as a set ha1, ..., aki={λ1a1+... +λkak|λi∈Z≥0},with gcd(a1, ..., ak) = 1. This object has been thoroughly studied in the last years, when a significant number of problems concerning the description of these semigroups and some of its more interesting invariants have been tackled. Unless otherwise stated, all proofs which are not included can be found in [8, 19]. Given a numerical semigroup S, there are some invariants which will be of interest for us. The most relevant will be the set of gaps, noted G(S), and defined by G(S) = Z≥0\S, which is a finite set. Its cardinality will be noted g(S) and its maximum f(S), the so–called Frobenius number. The Ap´ery set of Swith respect to an element s∈Scan be defined as Ap(S, s) = {0, w0, ..., ws−1} where wiis the smallest element in Scongruent with imodulo s. In particular, for semigroups with two generators, the invariants g(S) and f(S) and the relevant Ap´ery sets are fully determined. Lemma 3. Let S=ha1, a2i. Then g(S) = 1 2(a1−1)(a2−1) f(S) = (a1−1)(a2−1) −1 Ap(S, ai) = {0, aj,2aj, ..., (ai−1)aj} 3. The number of integral points inside a right triangle Let us consider then a right triangle determined by the positive coordinate axes and the line ax +by =c, a, b, c ∈Zand gcd(a, b) = 1, where we will assume a < b, with no loss of generality. Take the set: T=(x, y)∈Z2 ≥0|ax +by ≤c and let us define the numerical semigroup associated to our triangle as S=ha, bi. Stherefore verifies that its Frobenius number is f(S) = ab −(a+b). Let us perform the following partition on our set T: B0=(x, y)∈Z2 ≥0|ax +by ≤c, 0≤x < b B1=(x, y)∈Z2 ≥0|ax +by ≤c, b ≤x < 2b . . .. . . Bi=(x, y)∈Z2 ≥0|ax +by ≤c, ib ≤x < (i+ 1)b . . .. . . Bk=(x, y)∈Z2 ≥0|ax +by ≤c, kb ≤x 4 G. M ´ ARQUEZ–CAMPOS, J.L. RAM´ IREZ–ALFONS´ IN, AND J.M. TORNERO where k=⌊c/(ab)⌋. As our aim is to find #T, and it is plain that: #T= #B0+ #B1+... + #Bk−1+ #Bk, we can reduce our problem to that of finding #Bi, for i= 0, ..., k. Lemma 4. Under the previous assumptions, if k > 0, #B0=a+b−ab + 1 2+c=1−f(S) 2+c Proof. We will actually show that S∩[0, c]1:1 ←→ B0. Given a pair (x, y)∈B0we define its corresponding element in S∩[0, c] to be n=ax +by. In the same way, given n∈S∩[0, c] it is clear that we must have a representation n=ax +by and we can in fact assume 0 ≤x < b (if otherwise, we can move part of ax into the by summand until x < b). Let us assume that we have such a representation (that is, with 0 ≤x < b) and we will prove that then the pair (x, y) must be unique, which will establish the bijection. Should we have n=ax0+by0=ax1+by1,with 0 < x0, x1< b, we must have a(x0−x1) = b(y1−y0) and, as gcd(a, b) = 1, this means b|(x1−x0), which in turn implies x0=x1. Note that the case x0=x1= 0 leads directly to y0=y1as desired. Note that k > 0 is equivalent to c≥ab, which also yields c > f(S). Therefore, after Lemma 3, #B0= #S∩[0, c]= #S∩[0, f(S)]+c−f(S) =ab −(a+b) + 1 2+c−ab −(a+b) =a+b−ab + 1 2+c.  INTEGRAL POINTS IN RATIONAL POLYGONS 5 Simple as it is, this case is the basic argument for the whole process. Now, if we want to compute #B1, we just move our triangle, so that (b, 0) is now at the origin. Similarly, the line ax +by =cis moved, as in the picture: So, with a little abuse of notation, let us redefine: B1=(x, y)∈Z2 ≥0|ax +by ≤c1,0≤x < b where c1=c−ab (obviously this only makes sense if c > ab). Assuming k > 1 we have, following the same way: #B1= # (S∩[0, c1]) = #S∩[0, c −ab] =ab −(a+b) + 1 2+c−ab −(ab −(a+b) + 1) =a+b−3ab + 1 2+c. We can of course go along the same lines for computing #Bifor i= 1, ..., k −1, where k=⌊c/(ab)⌋, rewriting ci=c−iab, whenever c > iab and we will find: #Bi= # (S∩[0, ci]) = #S∩[0, c −iab] =ab −(a+b) + 1 2+c−iab −(ab −(a+b)) =(a+b)−(1 + 2i)ab + 1 2+c We have then arrived at the nutshell of the problem: the set Bk. After we have moved it to the origin, we have our renamed Bk: Bk=(x, y)∈Z2 ≥0|ax +by ≤ck. Now we might have ck< ab −(a+b). So we cannot proceed in the same way as before. We do know ck=c−kab, that is, ck=cmod ab, and from Lemma 3 we also know: Ap(S, a) = {0, b, 2b, ..., (a−1)b} and therefore {w∈Ap(S, a)|w≤ck}=nib i= 0,1, ..., jck bko On the other hand, if i∈ {0, ..., ⌊ck/b⌋}, we have ib +ja ≤ck⇐⇒ j≤ck−ib a, 6 G. M ´ ARQUEZ–CAMPOS, J.L. RAM´ IREZ–ALFONS´ IN, AND J.M. TORNERO and then S∩[0, ck] = {ib +ja ≤ck|i, j ∈Z≥0} =ib +ja i∈n0, ..., jck bko, j ≤ck−ib a = ⌊ck/b⌋ X i=0 ck−ib a+ 1 Adding up all of these computations, we arrive to our result. In the previous conditions: #T= #B0+ #B1+... + #Bi+... + #Bk−1+ #Bk =a+b−ab + 1 2+c+... +(a+b)−(1 + 2i)ab + 1 2+c+ +... + ⌊ck/b⌋ X i=0 ck−ib a+ 1 = k−1 X i=0 (a+b)−(1 + 2i)ab + 1 2+c+ ⌊ck/b⌋ X i=0 ck−ib a+ 1 =−ab 2k2+a+b+ 1 + 2c 2k+ ⌊c−kab b⌋ X i=0 c−kab −ib a+ 1 where k=⌊c/(ab)⌋. Or equivalently, by using the Euclidean division: c=q·ab +r we obtain #T=−ab 2q2+a+b+ 1 + 2c 2q+ ⌊r/b⌋ X i=0 r−ib a+ 1. This proves Theorem 2. Example. Let us do a simple example to illustrate the process, considering the triangle defined by the line 3x+ 7y= 46. Following Theorem 2 we have k=46 3·7= 2, that is, #T=−3·7 222+3 + 7 + 1 + 2 ·46 2·2+ ⌊46−2·3·7 7⌋ X i=0 46 −2·3·7−i·7 3+ 1= 63. Let us see the actual counting: INTEGRAL POINTS IN RATIONAL POLYGONS 7 In the picture we have put different symbols for the different sets Bj, following the process. Round points correpond to B0. There are 41 of them, as predicted by the formula: #B0=a+b−ab + 1 2+c=3 + 7 −3·7 + 1 2+ 46 = 41. Crossed points correspond to points in B1: #B1=a+b−3ab + 1 2+c=3 + 7 −3·3·7 + 1 2+ 46 = 20. And finally the square points are those of B2: #B2= ⌊ck b⌋ X i=0 ck−ib a+ 1=46 −42 3+ 1 = 2. 4. Applications (I): Integral points in general triangles Our aim in this section is to give a result (in some sense in the spirit of Pick’s theorem) to compute the number of integral points inside a generic triangle. This, of course, is enough to compute the number of integral points inside polygons (not necessarily convex) defined by rational vertices. But we will not address here the problem of dividing a polygon into triangles [5, 10]. The important point here is that, in order to compute the number of integral points of such a polygon, it suffices with rectangles and right triangles of a particular type. Of course rectangles can be divided in two right triangles, but this brings no substantial computational simplification to our problem. From now on, a rectangle whose sides are parallel to the coordinate axes will be called a stable rectangle. Computing the number of integral points inside a stable rectangle is very easy. Lemma 5. Let α1< β1and α2< β2be real numbers. Let R⊂R2be the stable rectangle with vertices (α1, α2)and (β1, β2). Then #(R∩Z2) = (⌊β1⌋ − ⌈α1⌉+ 1) ·(⌊β2⌋ − ⌈α2⌉+ 1) Similarly, a right triangle whose orthogonal sides are parallel to the coordinate axes will be called a stable right triangle. The computation of the number of integral points inside a stable right triangle can be easily achieved from Theorem 2, as we shall show now. Assume we have such a triangle Tdefined by rational vertices (Ais the vertex at which Thas its right angle): A= (α, β), B = (α, γ), C = (δ, β), and we can assume, up to symmetry, α < γ,β < δ. Furthermore, it is clear that, as for counting integral points is concerned, we can substitute α7−→ ⌈α⌉, β 7−→ ⌈β⌉, and the number of integral points does not change by traslations of integral vectors, hence we can in fact assume A= (0,0). 8 G. M ´ ARQUEZ–CAMPOS, J.L. RAM´ IREZ–ALFONS´ IN, AND J.M. TORNERO After translating the triangle T, we can write the hypothenuse of the new triangle as ax +by =c, where we can assume a, b, c ∈Z, gcd(a, b, c) = 1. That is, B= (0, c/b), C= (c/a, 0). Mind that aand bneed not to be coprime in this set–up. But, in order to apply Theorem 2, we should have gcd(a, b) = 1. Let d= gcd(a, b). There are two possibilities: (1) d= 1. We can apply Theorem 2. (2) d > 1. As gcd(d, c) = 1 clearly there are no integral points in the hypothenuse, as any such point (x, y) must verify ax +by ∈Zd. So we are going to change the triangle T, moving the hypothenuse in a parallel way towards A, until the new triangle has at least some chance to have one integral point in the hypothenuse. This is the triangle T′defined by ax +by =c′, where c′=⌊c/d⌋d. It is clear that with such construction #(T∩Z2) = #(T′∩Z2) and so #(T∩Z2) can be computed counting the number of integral points in the stable triangle defined by a dx+b dy=c′ d=jc dk, that is, using Theorem 2. As we shall see later, in related problems (as, for instance, the problem of computing the number of integral points inside a polygon), we might have to compute the number of points in the sides of a right stable triangle. To do this, note that: •The number of integral points in the orthogonal sides can be easily computed: in the segment limited by (a, b) and (a, c), say with b < c (any other case is obviously symmetric), the number of integral points is (⌊c⌋ − ⌈b⌉+ 1) ·1Z(a), where 1Z(a) is the indicator function of Z. •The number of integral points in the line ax +by =cis the number of representations of cinside the semigroup S=ha, bi. This number is known as the denumerant of cin S[19]. INTEGRAL POINTS IN RATIONAL POLYGONS 9 It is easy to see that this denumerant has to be either ⌊c/(ab)⌋or ⌊c/(ab)⌋+ 1, that is, kor k+ 1 with the notation of the previous section, assuming c∈S(obviously it is 0 otherwise). This is because c(or ci) must be representable and from Lemma 4 there must exist exactly one representation whose coefficients are in B0(respectively Bi). This holds true for B0,...,Bk−1but not necessarily for Bk(because ckmight not be in S), hence the two possible cases. More precisely, we have the following result (see [18] for the original proof in Romanian, [6] for a shorter and easier one): Theorem 6. Under the previous asumptions, let a′and b′be the only integers veryfing 0< a′< b, a ·a′=−cmod b 0< b′< a, b ·b′=−cmod a Then the denumerant of cin Sis given by d(c;a, b) = c+a·a′+b·b′ ab −1 In the sequel, when we are interested in the points inside a right triangle Twe will write #Tint and if we want the points excluding only the hypothenuse we will denote this cardinal by #Thyp. Finally, then, let us show how to compute the integral points in a generic triangle using stable rectangles and right triangles (and hence, Theorem 2). Assume we are given a triangle T, given by A1= (α1, β1), A2= (α2, β2), A3= (α3, β3), and let us call x0= min i=1,2,3αi, x1= max i=1,2,3αi; y0= min i=1,2,3βi, y1= max i=1,2,3βi; We consider the (stable right) rectangle RTdetermined by nV1= (x0, y0), V2= (x1, y0), V3= (x0, y1), V4= (x1, y1)o. It is clear that it must hold Vi=Ajfor some i= 1,2,3,4 and j= 1,2,3. Depending on the relative position of the maximal vertices, the situation must be one of these four (up to rotation and flip, if necessary): •Only one of the vertices of RTis a vertex of T. Then it is clear that: #T= #RT−#Thyp 1−#Thyp 2−#Thyp 3.