[math-fun] Square-free subsets of the integer grid
We've been discussing the fact that squares are the only regular polygons on the integer grid. I'd like to poke some holes in that. The question is how many holes are needed? In other words, I want to remove just enough points from the integer grid (aka square lattice on the XY plane, aka gaussian integers) such that no square polygons exist on the remaining points. I'm mostly interested in a grid that extends forever in all four quadrants. (It's not interesting that if you remove points from everwhere but a line you can't have any squares.) Of course no repeating pattern of removals will work. I'm pretty sure the proportion that are removed must increase without limit as the grid gets larger, as happens with gaussian primes. (Gaussian primes themselves obviously allow squares, due to their fourfold symmetry. Whether they allow squares in just a single octant (e.g. A+Bi where A is a non-negative integer and B is a non-negative integer no greater than A) is an interesting question, but doesn't involve a grid that extends forever in all eight octants.) I'd like to maximize the asymptotic density, i.e. have as few holes as possible out to each distance, roughly speaking. Has anyone ever worked on this before? Keep in mind that the sides of squares on the integer grid don't need to be parallel to, or at a 45 degree angle to, the axes. Squares can sneak in at lots of different angles.
Directly relevant, it seems to me, is the sequence https://oeis.org/A240443, which asks how many points may be selected from an nxn square grid without forming a square. Unfortunately only the first 9 values are known. Surely somebody here can do the hefty search required to nail down A240443(10); we want to know it because this sequence's start coincides with three other sequences on OEIS, and the next element might distinguish it. Apparently a configuration of 50 points can be found on the 10x10 grid without permitting a square, but a 51-point configuration is not known. On Sat, Aug 12, 2017 at 11:52 AM, Keith F. Lynch <kfl@keithlynch.net> wrote:
We've been discussing the fact that squares are the only regular polygons on the integer grid. I'd like to poke some holes in that. The question is how many holes are needed?
In other words, I want to remove just enough points from the integer grid (aka square lattice on the XY plane, aka gaussian integers) such that no square polygons exist on the remaining points. I'm mostly interested in a grid that extends forever in all four quadrants. (It's not interesting that if you remove points from everwhere but a line you can't have any squares.) Of course no repeating pattern of removals will work. I'm pretty sure the proportion that are removed must increase without limit as the grid gets larger, as happens with gaussian primes. (Gaussian primes themselves obviously allow squares, due to their fourfold symmetry. Whether they allow squares in just a single octant (e.g. A+Bi where A is a non-negative integer and B is a non-negative integer no greater than A) is an interesting question, but doesn't involve a grid that extends forever in all eight octants.)
I'd like to maximize the asymptotic density, i.e. have as few holes as possible out to each distance, roughly speaking.
Has anyone ever worked on this before?
Keep in mind that the sides of squares on the integer grid don't need to be parallel to, or at a 45 degree angle to, the axes. Squares can sneak in at lots of different angles.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Allan Wechsler -
Keith F. Lynch