The skew corner-free set bound

About 3 years old · traced to

Let [n]={1,…,n}[n]=\{1,\ldots,n\}, and let S⊆[n]2S\subseteq[n]^2 be skew corner-free, meaning that SS contains no three points of the form

(x,y), (x,y+δ), (x+δ,y′)(x,y),\ (x,y+\delta),\ (x+\delta,y')

with δ≠0\delta\ne0. The skew corner-free set conjecture. For every ε>0\varepsilon>0, one has

∣S∣≤O(n1+ε).|S|\le O(n^{1+\varepsilon}).

The trivial construction gives ∣S∣≥n|S|\ge n, while Petrov's construction gives ∣S∣≥Ω(nlog⁡n/log⁡log⁡n)|S|\ge\Omega(n\log n/\sqrt{\log\log n}). The best upper bound stated here is only O(n2/(log⁡log⁡n)0.0137⋯)O(n^2/(\log\log n)^{0.0137\cdots}), so the conjectured near-linear bound remains open.

References

Primary source

Kevin Pratt, “On generalized corners and matrix multiplication”, arXiv:2309.03878 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.