The number of co-circular four tuples

Question

Let $A,B ⊂ \mathbb{R}$ such that $|A| = |B| = n$. What is the best-known upper bound on the number of four-tuples in $A \times B$ where the four points are co-circular, they lie on the same circle?

Answer 1

Consider the number of triples from this set that lie on a circle. There are at most n points that lie on a line passing through the set (since the point set is a rectangular array), so given two points, there are at least $n^2 - n$ choices for a third point. So there are at least $n^2(n^2-1)(n^2-n)/6$ choices for triples, which in magnitude is not far from the maximum of $\binom{n^2}{3}$ possibilities.

Now suppose that for three given points on a circle, that circle has k points from the set. Then each of $\binom{k}{3}$ tuples gives rise to the same set of $\binom{k}{4}$ quadruples on the circle. If $k$ is $3$, this amount is $0$ quadruples, and otherwise it is $(k-3)/4$ many quadruples for each triple. $k$ can be no larger than $2n$ because the point set is a rectangular array, so one can never have more than $n/2$ times as many concyclic quadruples as triples, so a weak upper bound is $\frac{n}{2} \cdot \binom{n^2}{3}$. As remarked in a comment, the actual order is likely more $\binom{n^2}{3}$ as one should not expect $k$ to be much larger than a constant bound often. Since the point set is a rectangular array one gets $\binom{n}{2}^2$ as an immediate lower bound for number of such quadruples.

Gerhard "Running Circles Around The Problem" Paseman, 2018.07.10.

Answer 2

Incidence geometry can be used to prove that any finite set $P \subset \mathbb R^2$ with $O(|P|^{1/2})$ points on a single circle determines $O(|P|^3)$ cocircular quadruples. Since your grid point set satisfies this condition, it follows that there are $\ll n^6$ cocircular quadruples. Is this tight?

The argument is similar to that which uses the Szemeredi-Trotter Theorem to show that a set of points in the plane with no more than $|P|^{1/2}$ on a line determine $O(|P|^2 \log |P|)$ collinear triples.

Here is a rough proof. For a fixed point set $P$, let $C_k$ denote the set of all circles containing at least $k$ points from $P$. You can use Pach-Sharir's generalisation of Szemeredi-Trotter for pseudolines to prove that $$|C_k| \ll \frac{|P|^3}{k^5} + \frac{|P|}{k} \ll \frac{|P|^3}{k^5}, $$ where the last inequality follows from the assumption that $k \ll |P|^{1/2}$. Actually there is a hidden assumption here that $k$ is larger than some absolute constant, but then we can count cocircular quadruples on such poor circles by some trivial arguments.

Now, dyadically decompose the number of cocircular quadruples and apply the bound on $|C_k|$ to complete the proof.

$$|\{ \text{all cocircular quadruples}| \leq \sum_{j \geq 3} \sum_{C : 2^{j-1} \leq | C \cap P| < 2^j} |C \cap P|^4 \ll \sum_j (2^j)^4 \frac{|P|^3}{(2^j)^5} \ll |P|^3.$$