8
$\begingroup$

A century ago, Dudeney asked to place $16$ pawns on a chessboard with no three on a line:


          Dudeney_16
As described by David Eppstein,1 the maximum number $g_3(n)$ points that can be placed on an $n \times n$ integer grid, avoiding three points on a line, satisfies $$ \tfrac{3}{2} n - o(n) \le g_3(n) \le 2 n \;.$$

My question is:

Q. What are bounds on $g_4(n)$, the maximum number of points that can be placed on an $n \times n$ integer grid, no three on a line, no four cocircular?


          Dudeney_8
          Perhaps no $4$ of the $6$ points (right figure) are cocircular?
          Added: @AaronMeyerowitz shows that in fact $4$ points are cocircular.


The question can be generalized to avoiding points lying on an algebraic curve of degree $d$.


1 Eppstein, David. Forbidden Configurations in Discrete Geometry. Cambridge University Press, 2018. Chapter 9, pages 72–75. Cambridge link.

$\endgroup$
5
  • $\begingroup$ You should adjust the number $d+2$ upward, as a curve of degree $d$ has $\binom{d+1}{2}-1$ degrees of freedom. If you make this adjustment, then, I believe, that the answer should be $o(n)$ for $d\geq d_0$, but that is certainly wide open. $\endgroup$
    – Boris Bukh
    Commented Dec 24, 2018 at 15:25
  • $\begingroup$ @BorisBukh: Thanks for the correction. $\endgroup$ Commented Dec 24, 2018 at 15:30
  • 3
    $\begingroup$ In your 6 point diagram, any point on the central line is equidistant from the two on the left and also equidistant from the two on the right. Some point is equidistant from all 4 of them. $\endgroup$ Commented Dec 25, 2018 at 5:50
  • $\begingroup$ @AaronMeyerowitz: Nice reasoning! Maybe $g_4(4) = 5$... $\endgroup$ Commented Dec 25, 2018 at 14:14
  • 1
    $\begingroup$ Maybe also of interest: Achim Flammenkamp's solutions to the no-3-in-a-line problem $\endgroup$ Commented Dec 26, 2018 at 15:11

1 Answer 1

2
$\begingroup$

this should be considered as a comment:

There seems to be a strong relation of the "no 4 points cocircular" problem to pythagorean triples:

Taking $(0,0)$ as one of the corners of Pythagorean triangles excluding that corner from the pointset to be generated, yields eight cocircular gridpoints, of which not more that three can be in the final pointset, thus yielding as a first upper bound marked points, namely $\frac{3}{2}\#PT_L$ where $PT_L$ denotes the number of Pythagorean triples $\lbrace (a,b,c)\ |\ 0\lt a\lt b\lt c\le L\rbrace$ with given upper bound $L$ on the length of the hypotenuse $c$.

A further refinement of the estimate is possible by taking into account the number of different (primitive) Pythagorean triples with equal length of the hypotenuse; that number seems to be $2^{k-1}$, where $k$ is the number of $c$'s primefactors of the form $4p+1$ (cf e.g. number of primitive pythagorean triples with common hypotenuse.

So, because of the apparent relation to number theoretic questions, there seems little hope to find sharp upper bounds on the maximal number of points in a square grid, of which no four are co-circular.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .