On Subsets of Lattice Cubes Avoiding Affine and Spherical Degeneracies

Abstract For integers $$1&lt; k &lt; d-1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>&lt;</mml:mo> <mml:mi>k</mml:mi> <mml:mo>&lt;</mml:mo> <mml:mi>d</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> and $$r \geqslant k+2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>r</mml:mi> <mml:mo>⩾</mml:mo> <mml:mi>k</mml:mi> <mml:mo>+</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> , we establish new lower bounds on the maximum number of points in $$[n]^d$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mo>[</mml:mo> <mml:mi>n</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> <mml:mi>d</mml:mi> </mml:msup> </mml:math> such that no r lie in a k -dimensional affine (or linear) subspace. These bounds improve on earlier results of Sudakov-Tomon and Lefmann. Further, we provide a randomised construction for the no-four-on-a-circle problem posed by Erdős and Purdy, improving Thiele’s bound. We also consider the random construction in higher dimensions, and improve the bound of Suk and White for $$d \geqslant 4$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>⩾</mml:mo> <mml:mn>4</mml:mn> </mml:mrow> </mml:math> . In each case, we apply the deletion method, using results from number theory and incidence geometry to solve the associated counting problems.