betaFeedback

WorksMathematics

A 19/519/5 lower bound for the four-dimensional Erdős box problem

Abstract

For every power q≥2q\ge2 of~22, we construct a box-free subset of [q5]4[q^5]^4 with q19q^{19} points, improving the lower-bound exponent in the four-dimensional Erdős box problem from 15/415/4 to 19/519/5. In fact, [q5]4[q^5]^4 partitions into qq isomorphic box-free sets. The proof uses a finite-field rectangle lemma and orthogonality in a four-dimensional bilinear space. We also deduce a uniform bound f4(n)≥2−19/20n19/5f_4(n)\ge2^{-19/20}n^{19/5} and a lower bound for grid-coloring numbers.

Introduction

A box in a product V1×⋯×VrV_1 \times\cdots\times V_r is a set A1×⋯×ArA_1 \times\cdots\times A_r with ∣Ai∣=2|A_i| = 2 for all ii. A set is box-free if it contains no box. Let fr(n)f_r(n) be the maximum size of a box-free subset of [n]r[n]^r, where [n]={1,…,n}[n] = \{1,\ldots,n\}. Equivalently, fr(n)f_r(n) is the maximum number of edges in an rr-partite rr-uniform hypergraph with nn vertices in each part and no copy of K2,…,2(r)K^{(r)}_{2,\ldots,2}.

Erdős [3] proved that fr(n)=O(nr−1/2r−1)f_r(n) = O(n^{r-1/2^{r-1}}) and conjectured that this is the correct order of magnitude. The conjecture is known for r=3r = 3 [6]. For r=4r = 4, Gunderson, Rödl, and Sidorenko [5] obtained the lower bound f4(n)=Ω(n15/4)f_4(n) = \Omega(n^{15/4}), subsequently recovered by Conlon, Pohoata, and Zakharov [1] and Gordeev [4]. We improve the lower-bound exponent to 19/519/5.

Theorem 1. For every power q≥2q \ge2 of 2, there is a box-free subset of [q5]4[q^5]^4 of size q19q^{19}. Moreover, [q5]4[q^5]^4 partitions into qq isomorphic box-free subsets.

The construction uses the inverse of the permutation Q(x)=xq2+qQ(x) = x^{q^2+q} of K=Fq3K = \mathbb{F}_{q^3}. A rectangle lemma shows that four points of the form Q−1(ui+vj)Q^{-1}(u_i+v_j) are either collinear or affinely independent over Fq\mathbb{F}_q. This dichotomy, together with a bilinear pairing, rules out boxes. We give the lemma and the proof, then deduce the uniform lower bound and the coloring consequence.

A finite-field rectangle lemma

Fix a power q≥2q \ge2 of 2, and write k=Fqk = \mathbb{F}_q and K=Fq3K = \mathbb{F}_{q^3}. The relative trace and norm are

Tr⁡(x)=x+xq+xq2,N⁡(x)=xq2+q+1.\operatorname{Tr}(x) = x + x^q + x^{q^2}, \qquad\operatorname{N}(x) = x^{q^2+q+1}.

Since Tr⁡(α)=α\operatorname{Tr}(\alpha) = \alpha for α∈k\alpha\in k, the trace pairing (x,y)↦Tr⁡(xy)(x,y) \mapsto\operatorname{Tr}(xy) is nondegenerate: for x≠0x \ne0, take y=x−1y = x^{-1}. Also, N⁡(x)=0\operatorname{N}(x) = 0 if and only if x=0x = 0.

Set Q(x)=xq2+qQ(x) = x^{q^2+q}. Expanding N⁡(x+y)\operatorname{N}(x+y) and using xQ(x)=N⁡(x)∈kxQ(x) = \operatorname{N}(x) \in k gives

Tr⁡((x+y)(Q(x)+Q(y)))=N⁡(x+y)(x,y∈K).(1)\operatorname{Tr}\left((x+y)(Q(x)+Q(y))\right) = \operatorname{N}(x+y) \qquad(x,y \in K). \tag*{(1)}

Thus Q(x)=Q(y)Q(x) = Q(y) implies x=yx = y, so QQ permutes KK. Its polarization

P(x,y)=Q(x+y)+Q(x)+Q(y)=xqyq2+xq2yqP(x,y) = Q(x+y) + Q(x) + Q(y) = x^{q}y^{q^2} + x^{q^2}y^{q}

is symmetric and kk-bilinear, with P(x,x)=0P(x,x)=0. Applying (2.1) to x+yx+y and yy shows that Tr⁡(xP(x,y))=0\operatorname{Tr}(xP(x,y))=0. Moreover, P(x,y)=0P(x,y)=0 if and only if x,yx,y are linearly dependent over kk: when x≠0x\ne0, this equation is equivalent to (y/x)q=y/x(y/x)^q=y/x.

The next lemma gives the dichotomy used in the construction. We include the proof, following [6 Lemma 3.2].

Lemma 2. Let u0,u1,v0,v1∈Ku_0,u_1,v_0,v_1\in K, and put

Aij=Q−1(ui+vj)(i,j∈{0,1}).A_{ij}=Q^{-1}(u_i+v_j)\qquad(i,j\in\{0,1\}).

If u0≠u1u_0\ne u_1 and v0≠v1v_0\ne v_1, then either the four points AijA_{ij} are affinely independent over kk, or they are collinear and satisfy

∑i,jAij=0,∑i,jTr⁡(uiAij)≠0.\sum_{i,j} A_{ij}=0,\qquad\sum_{i,j}\operatorname{Tr}(u_iA_{ij})\ne0.

If u0=u1u_0=u_1 or v0=v1v_0=v_1, both sums vanish.

Proof. If u0=u1u_0=u_1 or v0=v1v_0=v_1, the entries occur in equal pairs and both sums vanish. Assume that u0≠u1u_0\ne u_1 and v0≠v1v_0\ne v_1, and set

a=A10+A00,b=A01+A00,c=∑i,jAij.a=A_{10}+A_{00},\qquad b=A_{01}+A_{00},\qquad c=\sum_{i,j}A_{ij}.

Then a,b≠0a,b\ne0 and A11=A00+a+b+cA_{11}=A_{00}+a+b+c. Summing Q(Aij)=ui+vjQ(A_{ij})=u_i+v_j and expanding gives

Q(c)+P(A00+a+b,c)+P(a,b)=0.(2)Q(c)+P(A_{00}+a+b,c)+P(a,b)=0. \tag*{(2)}

Multiplying by cc and taking the trace yields

N(c)=Tr⁡(cP(a,b)).N(c)=\operatorname{Tr}(cP(a,b)).

The kk-trilinear form (a,b,c)↦Tr⁡(cP(a,b))(a,b,c)\mapsto\operatorname{Tr}(cP(a,b)) is alternating, since it vanishes whenever two arguments coincide. If c≠0c\ne0, then N(c)≠0N(c)\ne0, so a,b,ca,b,c are linearly independent and the four points AijA_{ij} are affinely independent.

If c=0c=0, equation (2.2) gives P(a,b)=0P(a,b)=0. Hence b=λab=\lambda a for some λ∈k×\lambda\in k^\times, and the points are collinear. Finally, (2.1) gives

∑i,jTr⁡(uiAij)=Tr⁡((u0+u1)b)=λTr⁡(a(Q(A00+a)+Q(A00)))=λN(a)≠0.\begin{aligned} \sum_{i,j}\operatorname{Tr}(u_iA_{ij})=\operatorname{Tr}((u_0+u_1)b) \\ &=\lambda\operatorname{Tr}\bigl(a(Q(A_{00}+a)+Q(A_{00}))\bigr) \\ &=\lambda N(a)\ne0. \end{aligned}

The construction

Continue with kk, KK, QQ from Section 2. Equip W=K⊕kW=K\oplus k with the nondegenerate symmetric bilinear form

⟨(a,α),(b,β)⟩=Tr⁡(ab)+αβ,\langle(a,\alpha),(b,\beta)\rangle=\operatorname{Tr}(ab)+\alpha\beta,

and put e=(0,1)e=(0,1), so ⟨e,e⟩=1\langle e,e\rangle=1. For x=(u,w)x=(u,w) and y=(v,z)y=(v,z) in WW, define the pair-map Φ:W×W→W\Phi:W\times W\to W by

Φ(x,y)=(a,Tr⁡(au)+w+z),a=Q−1(u+v).\Phi(x,y)=\bigl(a,\operatorname{Tr}(au)+w+z\bigr),\qquad a=Q^{-1}(u+v).

Let V=W×kV = W \times k, so ∣V∣=q5|V| = q^5. Write a vertex as vp=(xp,ωp)v_p = (x_p,\omega_p), where xp=(up,wp)x_p = (u_p,w_p). Define χ:V4→k\chi: V^4 \to k by

χ(v1,v2,v3,v4)=⟨Φ(x1,x2),Φ(x3,x4)⟩+w1w2+w3w4+∑p=14ωp(3)\chi(v_1,v_2,v_3,v_4)=\langle\Phi(x_1,x_2),\Phi(x_3,x_4)\rangle+w_1w_2+w_3w_4+\sum_{p=1}^{4}\omega_p \tag*{(3)}

The pairing will make the two difference spaces of a box orthogonal. The asymmetric trace term in Φ\Phi forces a two-dimensional difference space to contain ee when both KK-coordinates vary; the terms w1w2+w3w4w_1w_2+w_3w_4 rule out the case when neither varies.

Proof of Theorem 1. In (3.1), the first three vertices and x4x_4 determine ω4\omega_4 uniquely for any prescribed value of χ\chi. Thus every fiber has q19q^{19} points. The translation ω4↦ω4+α\omega_4\mapsto\omega_4+\alpha carries S=χ−1(0)S=\chi^{-1}(0) onto χ−1(α)\chi^{-1}(\alpha) and preserves boxes. It therefore suffices to prove that SS is box-free.

Suppose that SS contains a box with vertices vp=(xp,ωp)v_p=(x_p,\omega_p), where xp=(up,wp)x_p=(u_p,w_p), p∈{1,2,3,4}p\in\{1,2,3,4\}, and i∈{0,1}i\in\{0,1\}. Comparing two corners differing only in part pp shows that xp(0)=xp(1)x_p^{(0)}=x_p^{(1)} would force ωp(0)=ωp(1)\omega_p^{(0)}=\omega_p^{(1)}. Since the vertices in each part are distinct, we have

xp(0)≠xp(1)(p=1,2,3,4).(4)x_p^{(0)}\ne x_p^{(1)}\qquad(p=1,2,3,4). \tag*{(4)}

For i,j,r,s∈{0,1}i,j,r,s\in\{0,1\}, put

Cij=Φ(x1(i),x2(j)),Crs′=Φ(x3(r),x4(s)),C_{ij}=\Phi\left(x_1^{(i)},x_2^{(j)}\right),\qquad C'_{rs}=\Phi\left(x_3^{(r)},x_4^{(s)}\right),

and define

L=span⁡k{Cij+C00:i,j∈{0,1}},L=\operatorname{span}_k\{C_{ij}+C_{00}:i,j\in\{0,1\}\},
L′=span⁡k{Crs′+C00′:r,s∈{0,1}}.L'=\operatorname{span}_k\{C'_{rs}+C'_{00}:r,s\in\{0,1\}\}.

The corner equations have the separated form

⟨Cij,Crs′⟩=hij+hrs′,(5)\langle C_{ij},C'_{rs}\rangle=h_{ij}+h'_{rs}, \tag*{(5)}

where

hij=w1(i)w2(j)+ω1(i)+ω2(j),hrs′=w3(r)w4(s)+ω3(r)+ω4(s).h_{ij}=w_1^{(i)}w_2^{(j)}+\omega_1^{(i)}+\omega_2^{(j)},\qquad h'_{rs}=w_3^{(r)}w_4^{(s)}+\omega_3^{(r)}+\omega_4^{(s)}.

Taking a difference in each index pair gives

⟨Cij+C00,Crs′+C00′⟩=0.\langle C_{ij}+C_{00},C'_{rs}+C'_{00}\rangle=0.

Thus L⊥L′L\perp L', and nondegeneracy gives

dim⁡kL+dim⁡kL′≤4.(6)\dim_k L+\dim_k L'\le4. \tag*{(6)}

Summing (3.3) over i,ji,j at r=s=0r=s=0 also gives

⟨∑i,jCij,C00′⟩=(w1(0)+w1(1))(w2(0)+w2(1)).(7)\left\langle\sum_{i,j}C_{ij},C'_{00}\right\rangle=(w_1^{(0)}+w_1^{(1)})(w_2^{(0)}+w_2^{(1)}). \tag*{(7)}

We claim that dim⁡kL≥2\dim_k L\ge2, and that e∈Le\in L whenever dim⁡kL=2\dim_k L=2. There are three cases. If neither u1u_1 nor u2u_2 varies, then (4) forces both w1w_1 and w2w_2 to vary. But ∑i,jCij=0\sum_{i,j} C_{ij}=0, contradicting (7).

If exactly one of u1,u2u_1,u_2 varies, the difference in the other coordinate is a nonzero multiple of ee. The difference in the varying coordinate has a nonzero KK-component. Since ∑i,jCij=0\sum_{i,j} C_{ij}=0, these two differences span LL. Hence dim⁡kL=2\dim_k L=2 and e∈Le\in L.

Suppose that both u1,u2u_1,u_2 vary, and let Aij=Q−1(u1(i)+u2(j))A_{ij}=Q^{-1}(u_1^{(i)}+u_2^{(j)}) be the KK-components of CijC_{ij}. If the four points AijA_{ij} are affinely independent, then dim⁡kL=3\dim_k L=3. Otherwise, Lemma 2 gives

∑i,jAij=0,σ=∑i,jTr⁡(u1(i)Aij)≠0.\sum_{i,j} A_{ij}=0,\qquad\sigma=\sum_{i,j}\operatorname{Tr}(u_1^{(i)}A_{ij})\ne0.

Consequently, ∑i,jCij=σe∈L\sum_{i,j} C_{ij}=\sigma e\in L. The projection of LL onto KK is one-dimensional and nonzero, while the kernel of that projection is keke. Thus dim⁡kL=2\dim_k L=2 and e∈Le\in L.

The same claim holds for L′L'. By (6), both spaces have dimension 2 and contain ee. Their orthogonality gives the contradiction

0=⟨e,e⟩=1.0=\langle e,e\rangle=1.

Consequences

We first pass from powers of q5q^5 to arbitrary side lengths.

Corollary 3. For every integer n≥1n\ge1,

f4(n)≥2−19/20n19/5.f_4(n)\ge2^{-19/20}n^{19/5}.

Moreover, lim sup⁡n→∞f4(n)/n19/5≥1\limsup_{n\to\infty} f_4(n)/n^{19/5}\ge1.

Proof. If a box-free set S0⊆[N]4S_0\subseteq[N]^4 is restricted to independently chosen, uniformly random nn-element subsets of the four parts, where n≤Nn\le N, its expected size is ∣S0∣(n/N)4|S_0|(n/N)^4. Hence

f4(n)≥∣S0∣(n/N)4.f_4(n)\ge|S_0|(n/N)^4.

For n≥32n\ge32, let qq be the largest power of 2 with q5≤nq^5\le n, and write n=μq5n=\mu q^5, where 1≤μ<321\le\mu<32. Embedding the construction at qq and sampling the construction at 2q2q give

f4(n)≥max⁡{μ−19/5,μ1/52}n19/5≥2−19/20n19/5,f_4(n)\ge\max\left\{\mu^{-19/5},\frac{\mu^{1/5}}{2}\right\}n^{19/5}\ge2^{-19/20}n^{19/5},

because the two coefficients agree at μ=21/4\mu=2^{1/4}, with the first decreasing and the second increasing. For 2≤n<322\le n<32, sampling at q=2q=2 gives f4(n)≥n4/2>2−19/20n19/5f_4(n)\ge n^4/2>2^{-19/20}n^{19/5}, while f4(1)=1f_4(1)=1. Finally, f4(q5)≥q19f_4(q^5)\ge q^{19} gives the limsup assertion.

For c≥1c\ge1, let R4(c)R_4(c) be the least integer nn such that every cc-coloring of [n]4[n]^4 contains a monochromatic box [2][2].

Corollary 4. For every power q≥2q\ge2 of 2, we have R4(q)>q5R_4(q)>q^5. For every integer c≥2c\ge2,

R4(c)>c532.R_4(c)>\frac{c^5}{32}.

In particular, R4(2)≥33R_4(2)\ge33.

Proof. The coloring in Theorem 1 gives R4(q)>q5R_4(q)>q^5. For c≥2c\ge2, let qq be the largest power of 2 not exceeding cc. Since q>c/2q>c/2, monotonicity gives R4(c)≥R4(q)>q5>c5/32R_4(c)\ge R_4(q)>q^5>c^5/32.

The known exponents 19/519/5 and 31/831/8 differ by 3/403/40. It remains open whether the upper exponent is attainable, whether the construction can be extended to more dimensions, and what the correct growth rate of R4(c)R_4(c) is.

References

  1. [1]D. Conlon, C. Pohoata, and D. Zakharov, Random multilinear maps and the Erdős box problem, Discrete Anal. (2021), Paper No. 17, 8 pp.arxiv.org/abs/2011.09024
  2. [3]P. Erdős, On extremal problems of graphs and generalized graphs, Israel J. Math. 2 (1964), 183–190.DOI
  3. [4]A. Gordeev, Combinatorial Nullstellensatz and Turán numbers of complete r-partite r-uniform hypergraphs, Discrete Math. 347 (2024), no. 7, Paper No. 114037; corrigendum, Discrete Math. 348 (2025), no. 4, Paper No. 114417.DOI
  4. [5]D. S. Gunderson, V. Rödl, and A. Sidorenko, Extremal problems for sets forming Boolean algebras and complete partite hypergraphs, J. Combin. Theory Ser. A 88 (1999), no. 2, 342–367.DOI
  5. [6]D. Menezes, The three-dimensional Erdős box problem has exponent 11/4, arXiv preprint arXiv:2609.22381v2 [math.CO] (2026).arxiv.org/abs/2609.22381

Paper details

vlnc:W_vjdugr74
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents