From: rusin@vesuvius.math.niu.edu (Dave Rusin) Subject: Re: find the Maximum Area? [LONG!] Date: 8 Nov 1999 06:33:47 GMT Newsgroups: sci.math Keywords: largest square with 3 interior lattice points Lacking a worthwhile project for the weekend, I tackled an unanswered question from this newsgroup: In article <7vg3hs$bj4$1@nnrp1.deja.com>, wrote: >The area of the largest square that contains exactly 3 lattice points >in its interior is closest to >A. 4.0 >B. 4.2 >C. 4.5 >D. 5.0 >E. 5.6 I believe the correct answer is "D"; the area is exactly 5. In general we expect the number of lattice points in a convex body to be roughly the same as the area, but the correspondence is not all that precise, especially for small figures. So I find this question to be an interesting opportunity to think about how to handle such topics. The method I propose will find the maximum area of a square subject to containing N interior lattice points, but the work increases quickly with N. We will assume N=3 in what follows. Suppose I had an optimal square in my possession. To say that it's the largest one implies in particular that magnifying it (while maintaining center and orientation) would enclose at least one more lattice point, so there must be a lattice point on an edge e . There must also be a lattice point on the edge e' opposite e, or else we could expand a bit in a direction perpendicular to e. (Unless of course there is a lattice point on one of perpendicular edges f as well, in which case we use a small translation in another direction; details omitted.) Translate the square so the lattice point on e is (0,0); rotate as necessary to assume the opposite edge passes through a point (a,b) in the (closed) first quadrant. Reflect across the line y=x if need be, to assume b > a. I'll show that there is only a finite number of possible values for (a,b), so we may examine separately the families of squares passing through (0,0) and each one of these points; we will find the largest of these squares. Comparing the answers for all possible (a,b) will give the overall largest square touching (0,0) and containing 3 lattice points. To show there are only a few possible (a,b), we show the square can't be too big. Note that any square of length L contains a circle of diameter L, which in turn contains an open square parallel to the axes and with side L/sqrt(2), say (x1, x2) x (y1, y2). If the lengths of these intervals exceed 2, they each contain two integers, so that there are four lattice points in the oriented square, the circle, and the original square. So we conclude a square with at most three lattice points has side length L <= 2 sqrt(2) = sqrt(8), and so the area is at most 8. Moreover, no points in the closed square are a distance greater than 4 from each other. So, in addition to the other constraints on (a,b), we see it must lie in the disk of radius 4 at (0,0). The possible values of (a,b) which result are: (0,1) (0,2) (0,3) (0,4) (1,1) (1,2) (1,3) (2,2) (2,3) . (Obviously a similar method finds a finite list of possible "outer" points (a,b) for any target number N of interior lattice points.) So now let's take (a,b) as fixed and describe the family of squares touching (0,0) and (a,b) in opposite edges e and e' respectively. Let m be the slope[*] of the edges e and e', that is, the edges lie on the lines y = m x and y-b = m (x-a). And let (x1, m x1) be the vertex on e which has x1>0. The pair of numbers (m, x1) can be used as a parameter to distinguish the squares in this family. However, we will show that the pair (m, D) is an easier parameter to use, where D = x1 (m^2+1); this number can be interpreted as the x-intercept of the line containing this side of the square. [*](The exceptional case of axis-oriented squares is not much of a problem; such a square with edges on lines x=0 and x=a has area a^2 and either (a-1)^2 or a(a-1) interior lattice points -- never exactly 3.) First we describe the possible values of these parameters, that is, the set of pairs (m,x1) or (m,D) which really correspond to a square meeting our conditions. Note that the distance between these lines is L = |b-ma|/sqrt(1+m^2), so we can describe the square exactly: another vertex has x2 = x1 - |b-ma|/(1+m^2) and y2 = m x2 ; the other two have x3 = x1 + (m^2 a - m b)/(m^2+1) and x4 = x2 + (m^2 a - m b)/(m^2+1) and lie on y = m x + (b-ma). The statement that (0,0) is between the first two points is equivalent to x2 <= 0 <= x1 ; likewise the fact that (a,b) is between the last two vertices is equivalent to the inequalities a + m b < (m^2+1) x1 < a + m b + | b - m a | . It is convenient also to note that two points on a square can be no further than sqrt(2) L from each other, and thus (a^2+b^2) <= 2 (b-ma)^2/(1+m^2) . Simplify, factor, and conclude from this that m < (b-a)/(b+a). In particular, m <= 1 <= b/a, so that b-ma >= 0. So now we can describe the bounds on our parameter space: we must have x1 - (b-ma)/(1+m^2) <= 0 <= x1, and a+mb < (m^2+1) x1 < a+mb + (b-ma). Equivalently, we have a quadrilateral in the (m,D) plane: 0 <= D <= b - m a , and a + m b <= D <= (a+b) + m (b-a) It has vertices (m,D) = ( -(b+a)/(b-a),0 ), ( -a/b, (a^2+b^2)/b ), ((b-a)/(b+a), (a^2+b^2)/(a+b)), (-a/b, 0) . (In the case a=b the region is unbounded, but in this case we may use a reflection across the line y=x to assume that |m| <= 1, if we like.) These, then, are all the squares from which we may select the optimal one. "Optimal" means having the largest area L^2 = (b - a m)^2/(m^2+1) subject to the constraint of containing exactly three lattice points. This area increases until m = -a/b, then decreases across the rest of our parameter space, so essentially we just one the m closest to -a/b consistent with our lattice-point condition. All right, then, which points are included in which squares? In a square whose opposite sides include (0,0) and (a,b), the length of a side is at most sqrt(a^2+b^2), and so no point of the square can be a distance greater than sqrt(2)*sqrt(a^2+b^2) from the origin. That is, once (a,b) is fixed, there are only finitely many candidate lattice points which might be in any of these squares. For each of these lattice points (x,y), we can sketch the combinations of our parameters which give squares enclosing (x,y). This will partition the parameter space into pieces, on each of which we know which lattice points are in the square and which not. (I didn't work very hard to reduce the number of candidate interior points (x,y); one could easily do so, which would reduce the amount of partitioning which results in the discussion below. Just a little suggestion for anyone who want to push on to the cases N=4, 5, ... :-) ) A point (x,y) is in a square iff it lies in the four half-spaces defined by the linear functionals describing the edges: for our squares, we need y - m x > 0, y - m x - (b - m a) < 0, m y + x - (m^2+1) x1 < 0 , m y + x - (m^2+1) x2 > 0. In terms of our parameters (m,D), these are now the simple conditions (x) m < (y) and (a-x) m < (b-y) x + y m < D < (b+x) + (y-a) m In other words, inclusion of (x,y) limits points in the parameter space simply to lie in at most four half-planes! We sketch the portion of parameter space whose corresponding squares contain (x,y) by drawing four lines in the (m,D) plane and looking at the enclosed trapezium. Doing this calculation for each candidate (x,y) imposes a collection of these quadrilaterals; the number of lattice points contained in the interior of a square is the number of the quadrilaterals in which the corresponding parameter point (m, D) lies. We can draw all the bounding lines at once; this partitions the original parameter space into a set of 0-, 1-, and 2-cells, with the property that the squares corresponding to the parameter points in a cell contain exactly the same set of lattice points in their interior. For every open k-cell C (k=0, 1, or 2) in this partition, let n(C) be the number of lattice points in the interior of the squares whose parameters (m,D) lie in this cell. I claim that n(C) is at least as large as n(C') for any (k-1)-cell C' in the boundary of C; in particular, the squares with the fewest interior points are the ones corresponding to parameters which are 0-cells. I hope this is obvious because otherwise the proof is opaque... What I must do is show that if { (m_i, D_i) } is a sequence of parameter points converging to (m0, D0) , then n( (m0, D0) ) is no more than lim inf n( (m_i, D_i) ). But this is easy: passing to subsequences, we may assume n( (m_i, D_i) ) is constant, and (passing to another subsequence if necessary) may assume the squares with these parameters all contain precisely the same set of n( (m_i, D_i) ) lattice points. For any lattice point (x,y) not included in all these squares, we see that each of the (m_i, D_i) must violate one of the four constraints (x) m_i < (y) and (a-x) m_i < (b-y) x + y m_i < D_i < (b+x) + (y-a) m_i ; passing to _another_ subsequence, we may assume that all of them violate the same inequality among the four, e.g. we have x + y m_i >= D_i for all i. Taking finally the limit as i -> oo we get x+ y m0 >= D0 too, so (m0, D0) violates one of the four inequalities, and so the corresponding square also fails to include (x,y) in its interior. We conclude n( (m0, D0) ) <= n( (m_i, D_i) ) since it counts a subset of the lattice points the other squares contain. So let me summarize how this will help us. For all squares touching (0,0) and a fixed point (a,b), we have a certain set of say M lattice points which might be in the interior of those squares. These determine at most 4M lines cutting across the parameter space, intersecting in at most 2M^2 points (0-cells) C' of the parameter space. We identify which of these cells have n(C') <= 3. Testing all pairs of these we obtain the candidate 1-cells C on which n(C) <= 3 is also possible; we sample each to get a complete list of such 1-cells. Likewise we then find a list of candidate 2-cells C on which n(C) <=3; we sample each to get the 2-cells on which n(C) =3. In this way, we discover the entire subset of the parameter space corresponsing to squares with precisely three interior points. Finding the one with maximal area is then a simple optimization problem. (We just need the point with the largest m < -a/b and the one with the smallest m > -a/b.) Let's work this out for one of the larger cases, that of squares with (a,b) = (2,3) on their boundary. Our parameter space is the set of pairs (m,D) with 0 < D < 3 - 2m, 2 + 3m < D < 5 - m Now we partition this set. We begin by tabulating the M=44 points (x,y) which are close enough to both (0,0) and (2,3) that they could possibly lie in a square with these two points on opposite sides. (I did not pursue the tightest characterization of which points "could possibly" lie in such a square -- computers are so fast...; the right number is about M=30.) We therefore partition the parameter space with the 4M=176 lines given by the equations above. Actually many of these lines don't even intersect the parameter space, and not all are distinct; I count 39 lines crossing the region. These lines meet in 105 points within the given region. Those points represent 105 particular squares touching (0,0) and (2,3). We tabulate how many of the 44 lattice points (x,y) satisfy the four inequalities for each of these 105 squares (m,D). We find the answers vary from 4 (e.g. the square [0,3]x[0,3]) to 12 (e.g. the square with both (0,0) and (2,3) as vertices). In particular, we have n(C) > 3 for every 0-cell C, and thus on every 1- and 2-cell too. In other words, n(C) is at least 4 on every point of our parameter space, so there are NO squares touching (0,0) and (2,3) which have exactly three interior lattice points. Next we try the case of squares with (a,b) = (1,3) on their boundary. Our parameter space is the set of pairs (m,D) with 0 < D < 3-m, 1+ 3m < D < 4 - 2m There are now M=34 lattice points suitably close to both (0,0) and (a,b). We partition the parameter space with the 4M=136 lines, finding only 28 distinct lines among them which actually intersect the parameter space. They intersect in 55 points inside the parameter space. As before we count how many of the 34 points lie in the interior of the 55 corresponding squares, and get values between 4 and 9, but still no squares with as few as 3 interior points. (Note that in principle the squares corresponding to other points in the parameter space, besides these 55 0-cells, might have even more interior lattice points, but still never less than 4.) When (a,b)=(0,4) we find no more than 53 lattice points (x,y) as candidates and 143 0-cells in our parameter space. The corresponding squares have between 5 and 15 interior lattice points. When (a,b)=(0,3) we find 30 lattice points (x,y) to consider, 27 lines, and 64 0-cells in our parameter space. This time, the squares are smaller: they can have only as many as 8 interior points, AND they can have as few as 2 ! The only 0-cells with a count of 2 are those with (m,D) = (-1,0) and (1,3) ("diamonds"); all others correspond to squares with 4, 5, 6, 7, or 8 interior points. It follows that the only region in our parameter space where the interior-point count can be 3 would be along a 1-cell with endpoints at (-1,0) and (1,3). Unfortunately there is no such 1-cell. Thus there are again NO squares with EXACTLY three interior lattice points in this case. The analysis must be more detailed when there _are_ three-point squares. Let's illustrate with the case (a,b)=(1,2). I count 16 lattice points of interest. The parameter space consists of 14 0-cells, 28 1-cells, and 15 2-cells (all triangles, except for one little quadrilateral), if I've counted correctly. We compute the number of interior lattice points in the squares corresponding to these 57 different configurations; the results may be summarized as follows: The number of interior lattice points is precisely 1 when (m,D) = (0,1) or (0,2) 2 on the remainder of the closed triangle bounded by (0,1), (0,2), and (1/3,2/3) 2 at vertices (-1,0) and (-1,2) 2 on the closed parallelogram bounded by (-3,0), (-2,0), (-1,1), (-2,1) 3 on the remainder of the closed triangle bounded by (-3,0), (-1,0), and (-1,2) 3 on the rest of the closed line segments from (-1,0) to (0,1); (-1,1) to (0,1); (-1,1) to (0, 2); (-1,2) to (0,2). 4 on the rest of the parameter space (a quadrilateral bounded by (-3,0), (-1/2,0), (1/3, 5/3), and (-1/2, 5/2). ) Very well, then, we know precisely which of these squares enclose 3 interior points. Which has largest area? Well, area is (b - a m)^2/(m^2+1), and as we have noted increases as we approach m=-a/b from either side. In this case, that means the four combinations (-1/2,D) (with D=1/2,1,3/2,2) give the largest area, namely 5. For example, the first of these squares touches the points (0,0), (1,2), (1,1), and (-1,2); it encloses the lattice points (0,1) (0,2) and (-1,1). (For the record: the two squares with just one lattice point inside have area 4, and the largest squares with two lattice points in their interiors have area 9/2 -- e.g. the same diamond which is also tangent at (0,3).) When (a,b)=(2,2): 23 candidate points, crossing the parameter space with 20 distinct lines, yielding 38 0-cells, 94 1-cells, 56 2-cells. We find the single point m=0, D=2 (corresponding to the square [0,2]x[0,2]) has one interior point (namely (0,1)) and area 4. The points m=-1 and D=1 or 3 give squares (more diamonds, actually) with four interior points and area 8. All other points in the parameter space yield squares with at least 5 interior points. When (a,b)=(0,2): 11 candidate lattice points; 11 0-cells, 23 1-cells, 13 2-cells. The lattice-point count is 1 on the line from (-1,0) to (1,2) and at (0,0) and (0,2) 2 on the rest of the line from (0,0) to (0,2) 2 on the closed parallelogram with vertices (-1,0) (-1/2,1) (0,1) (-1/2,0) 2 on the closed parallelogram with vertices (1,2) (1/2,1) (0,1) (1/2,2) 3 on the rest of parallelogram (-1,0) (0,2) (1,2) (0,0) Here there is no maximum area among the squares with lattice-count 3, but taking squares with m -> 0 (and, say, D=1/2 or x1=1/2) gives squares with area increasing to 4, the lattice points enclosed being (0,1), (-1,1), and (-1,2). The axis-oriented squares give maximal area -- equal to 4 -- for squares containing 1 or 2 lattice points. When (a,b)=(1,1): the only candidate interior points are (0,1) and (1,0). Since a=b the parameter space is unbounded, but the same reasoning applies. There are three 0-cells, 5 1-cells, and 2 2-cells. The lattice-counting function equals 1 everywhere except along the line D=1, where it is zero: squares (such as the diamond) touching all four of the points (0,0) (1,1) (0,1) (1,0) contain no interior lattice point, and have area as great as 2; squares containing one lattice point (again diamonds will do) can also have area as great as 2. No squares contain 2 or more interior lattice points. When (a,b)=(0,1) there are no candidate interior points, i.e. all the squares contain zero lattice points. Max area= 1, achieved for the square [0,1]x[0,1] SUMMARY: We have investigated all squares containing (0,0) and another lattice point on opposite edges, for which these lattice points are at most 4 units distant. Only relatively few combinations contain fewer than four lattice points in their interiors. Here are the ones with largest area; most of them are either aligned with the axes ("square") or off by 45 degrees ("diamond"): 0 interior points: (a,b) = (0,1): area=1 (square) (a,b) = (1,1): area=2 (diamond) 1 interior point: (a,b) = (1,1): area=2 (diamond) (a,b) = (0,2): area=4 (square) (a,b) = (1,2): area=4 (square) (a,b) = (2,2): area=4 (square) 2 interior points: (a,b) = (0,2): area=4 (square) (a,b) = (1,2): area=9/2 (diamond) (a,b) = (0,3): area=9/2 (diamond) 3 interior points: (a,b) = (0,2): area=4-epsilon (near-square) (a,b) = (1,2): area=5 (example: lines with slopes of -1/2 through (0,0) and (1,2), and slopes of 2 through (1,1) and (-1,2). It encloses the points (0,1) (0,2) and (-1,1).) I also looked at some other small points (a,b), looking to see the minimum number of interior lattice points in a square touching (0,0) and (a,b) on opposite edges. Here are the data I collected: b=6 13,20 b=5 8,14 12 13 16 b=4 5,9 7 9 9,12 9,19 b=3 2,4,5 4 4,6 4,11 b=2 1 1,2 1,4,5 b=1 0 0,1 b=0 * a=0 a=1 a=2 a=3 a=4 The number in the (a,b) spot shows the minimum number of interior points in a square touching (a,b). When there are multiple numbers, there are squares with the smaller numbers of interior lattice points, but all are either aligned with the axes or "diamonds"; squares not of these orientations must have a number of interior points at least equal to the last number in the sequence. (Warning: these calculuations apply only to the 0-cells, so "gaps" in the numbers of interior points may be misleading.) This range of pairs (a,b) includes all squares which contain no axis-oriented square of edge length 3, and in particular includes all squares with fewer than 9 interior points. So a person who wanted to continue this analysis for squares with N=4, 5, 6, 7, or 8 interior points would only need to look in detail at the parameter spaces I worked on, together with the cases (a,b) = (1,4) and (3,3). (I have checked that the only squares with 8 interior points touching the point (0,5) is a diamond which also touches (1,4) and (2,3).) Of course, I'm not saying this is the easiest way to do this problem, but it seemed fruitful to me! dave