Combinatorial Nullstellensatz and No-Four-on-a-Circle Problem, Poster 25

The no-four-on-a-circle problem concerns determining the maximum number of points in an n-by-n grid that one can draw so that no four are on the same circle. The current known lower bound of the answer is n/4 by Thiele (1996).... [ view full abstract ]

The no-four-on-a-circle problem concerns determining the maximum number of points in an n-by-n grid that one can draw so that no four are on the same circle. The current known lower bound of the answer is n/4 by Thiele (1996). I use Combinatorial Nullstellenstaz to derive the following fact. Suppose n and m are positive integers such that m does not exceed n. Suppose further that there exists a set of m points such that no four are not on the same circle. Pick a pair of points in this set, say A and B. It follows that there are at least  2n-2m-3 when n<2m-3 and n(n-2m+4) otherwise points, called C, with the property that a circle determined by A, B and C contains exactly 2 points in the given points set. This fact may potentially lead to the improvement in the lower bound of the no-four-on-a-circle problem using mathematical induction.