betaFeedback

WorksMathematics

Triangle-Free Sets in Exact-Distance Hamming Graphs

Abstract

Let Tq(n,r)T_q(n,r) be the largest size of a vertex set inducing a triangle-free subgraph of the graph on [q]n[q]^n whose edges join words at Hamming distance rr. We study this quantity for fixed alphabet size and fixed distance, with particular emphasis on the ternary cube. Alphabet restriction transfers the binary fixed-distance theorem of Balogh, Chen, and Li to give Tq(n,2h)=Oh(qn/nh)T_q(n,2h)=O_h(q^n/n^h). We extend the known distance-one formula and distance-two order to arbitrary integer alphabet sizes, obtaining Tq(n,1)=2qn−1T_q(n,1)=2q^{n-1} and Tq(n,2)=Θq(qn/n)T_q(n,2)=Θ_q(q^n/n), and establish T3(n,4)=Θ(3n/n2)T_3(n,4)=Θ(3^n/n^2). For general fixed distance, we prove Tq(n,r)=Ωq,r ⁣(qnlog⁡nn(r+⌊r/2⌋)/2)(q≥3), T_q(n,r)=Ω_{q,r}\!\left( \frac{q^n\sqrt{\log n}}{n^{(r+\lfloor r/2\rfloor)/2}} \right)\qquad(q\ge3), while we show that Tq(n,r)=Ωq,r(qn/n⌊(q−1)r/q⌋)T_q(n,r)=Ω_{q,r}(q^n/n^{\lfloor(q-1)r/q\rfloor}) holds for prime-power qq and r≥2r\ge2 via the extended BCH parity-check constructions. At distance three, we construct coordinate weights avoiding bounded-coefficient three-term relations and obtain Tq(n,3)≥qn/[nexp⁡(Oq(log⁡n))]. T_q(n,3)\ge q^n/[n\exp(O_q(\sqrt{\log n}))]. Our main ternary construction combines cap partitions, multicolor triangle Ramsey colorings, and a quadratic map to obtain T3(n,3)=Ω ⁣(log⁡log⁡nlog⁡n 3n). T_3(n,3)=Ω\!\left( \frac{\log\log n}{\log n}\,3^n\right). A coordinate-line counting argument gives the complementary upper bound T3(n,3)≤(5/27+O(n−1))3nT_3(n,3)\le(5/27+O(n^{-1}))3^n, together with an explicit bound for every fixed q≥3q\ge3. Whether the ternary density tends to zero remains open.

Introduction and statement of results

Write [q]={0,1,…,q−1}[q]=\{0,1,\ldots,q-1\}. The qq-ary Hamming graph Hq(n)H_q(n) has vertex set [q]n[q]^n, and two vertices x,yx,y are connected if they are at Hamming distance dH(x,y)=1d_H(x,y)=1, i.e., the vectors of the corresponding vertices differ in exactly one coordinate. Note that Hq(n)H_q(n) is the Cartesian product of nn complete graphs KqK_q. A natural generalisation of the Hamming graph is the rr-distance Hamming graph Hq(n,r)H_q(n,r), which has vertex set [q]n[q]^n, and

xy∈E(Hq(n,r))⟺dH(x,y)=r.xy\in E(H_q(n,r))\Longleftrightarrow d_H(x,y)=r.

Our aim is to study the maximum size of a triangle-free set of vertices in the rr-distance graph of the Hamming graph.

Definition 1.1 (Maximum triangle-free set of vertices in Hq(n,r)H_q(n,r)).

Tq(n,r)=max⁡{∣A∣:A⊆[q]n and Hq(n,r)[A] is triangle-free}.T_q(n,r)=\max\{|A|:A\subseteq[q]^n\text{ and }H_q(n,r)[A]\text{ is triangle-free}\}.

This definition was introduced by Mukkamala and Ravi [16], who were mainly interested in the binary case q=2q=2.

In the terminology of extremal graph theory, it can also be expressed as the vertex Turán number

Tq(n,r)=ex⁡v(K3,Hq(n,r)),T_q(n,r)=\operatorname{ex}_v(K_3,H_q(n,r)),

namely the largest number of vertices inducing no copy of K3K_3 in the fixed host graph Hq(n,r)H_q(n,r). Vertex Turán problems for the Boolean cube were developed systematically by Johnson and Talbot [13], and related questions for the ternary cube were considered by Li and Hao [15]. The forbidden configurations in those works are embedded subcubes or prescribed small configurations, rather than equilateral triples in an exact-distance graph, so their results do not apply directly here.

There is an equivalent hypergraph formulation. Let Hq,n,r\mathcal{H}_{q,n,r} be the 3-uniform hypergraph on [q]n[q]^n whose hyperedges are the triples whose three pairwise Hamming distances are equal to rr. Then

Tq(n,r)=α(Hq,n,r).T_q(n,r)=\alpha(\mathcal{H}_{q,n,r}).

Thus the problem may also be viewed as an independence problem in a highly structured 3-uniform hypergraph, as well as a problem in coding theory.

Exact-distance graphs are closely related to graph powers, with adjacency prescribed by equality of distances rather than by an upper bound on distance. Their structure under Cartesian and other standard products, including exact-distance graphs of hypercubes, was investigated by Brešar, Gastineau, Klavžar, and Togni [7]. In the Boolean cube, forbidding all pairs at one prescribed distance is precisely the classical one-forbidden-distance code problem. Its development includes the subset-sum constructions of Cohen and Zémor [9] and the systematic forbidden-distance bounds of Bassalygo, Cohen, and Zémor [3]. The problem considered here is a genuinely higher-order relaxation: prescribed-distance pairs may occur abundantly, but the graph that they span is required to have clique number at most two.

The binary version arose explicitly from the recursive theta-body method of Castro-Silva, de Oliveira Filho, Slot, and Vallentin [8]. Mukkamala and Ravi developed direct combinatorial bounds, proving in particular a uniform estimate T2(n,r)=O(r2n/(n+1))T_2(n,r)=O(r2^n/(n+1)) for even r≤n/2r\le n/2, as well as exponentially small density when rr is a fixed positive fraction of nn, with r/n<2/3r/n<2/3 and rr is even [16]. For fixed distance, the decisive result is due to Balogh, Chen, and Li [2]. For a graph GG and an integer s≥2s\ge2, write

αs(G)=max⁡{∣A∣:A⊆V(G) and G[A] contains no Ks}.\alpha_s(G)=\max\{|A|:A\subseteq V(G)\text{ and }G[A]\text{ contains no }K_s\}.

Thus α2(G)=α(G)\alpha_2(G)=\alpha(G) and Tq(n,r)=α3(Hq(n,r))T_q(n,r)=\alpha_3(H_q(n,r)). In this notation, Balogh, Chen, and Li [2] proved that, for every fixed s≥2s\ge2 and h≥1h\ge1,

αs(H2(n,2h))=Θh,s(2nnh).(1)\alpha_s(H_2(n,2h))=\Theta_{h,s}\left(\frac{2^n}{n^h}\right). \tag*{(1)}

Alphabet restriction and the colorings developed below yield nonbinary extensions of this statement; see Corollary 3.3. Their proof brings together the theory of codes with one forbidden distance [3] and extremal estimates for sunflower-free set systems. Since H2(n,r)H_2(n,r) is bipartite when rr is odd, the binary rr-distance problem is therefore complete:

T2(n,r)={2n,r odd,Θr(2n/nr/2),r even and fixed.T_2(n,r)= \begin{cases} 2^n, & r\text{ odd},\\ \Theta_r(2^n/n^{r/2}), & r\text{ even and fixed}. \end{cases}

The passage from two symbols to three yields new phenomena. A binary equilateral Hamming triangle can use only coordinates in which exactly one of its three vertices differs from the other two. Over an alphabet of size at least three, a coordinate may instead contain three distinct symbols. This second local configuration creates triangles at every distance and, for q=3q = 3, couples the problem to affine lines, cap sets, and zero-sum Ramsey colorings. It is precisely here that the ternary theory separates from its binary precursor.

To highlight the distinction, suppose that x,y,z∈[q]nx,y,z \in[q]^n are pairwise at distance rr. Let ax,ay,aza_x,a_y,a_z count the active coordinates at which x,y,zx,y,z, respectively, are the unique exceptional symbols, and let dd count the coordinates at which all three symbols are different. Comparing the three pairwise distances gives

ax=ay=az=:a,2a+d=r.a_x = a_y = a_z =: a,\qquad2a+d=r.

This gives rise to the possible local types, indexed by 0≤a≤⌊r/2⌋0 \le a \le\lfloor r/2\rfloor, with active support of size r+ar+a. For q=2q=2 only the type a=r/2a=r/2 is available; for q≥3q\ge3 every type whose support size satisfies r+a≤nr+a\le n is realizable. This classification organizes both the general estimates and the constructions below.

Our first result is a universal upper bound for the qq-ary case.

Proposition 1.2 (Binary-subcube bound). For every fixed h≥1h\ge1 and every q≥2q\ge2,

Tq(n,2h)=Oh(qnnh).T_q(n,2h)=O_h\left(\frac{q^n}{n^h}\right).

At distance two, this upper bound is sharp for every fixed alphabet. At distance one, we have an exact formula. These give extensions of the work of Mukkamala and Ravi [16 Lemmas 4 and 5].

Theorem 1.3 (Distances one and two). For every fixed q≥2q\ge2,

Tq(n,1)=2qn−1andTq(n,2)=Θq(qnn).T_q(n,1)=2q^{n-1}\qquad\text{and}\qquad T_q(n,2)=\Theta_q\left(\frac{q^n}{n}\right).

The lower-bound construction for r=2r=2 is an independent set in Hq(n,2)H_q(n,2).

At Combinatorics 2026, A. Ravi asked whether

Tq(n,r)=Θq,r(qnn⌊r/2⌋)T_q(n,r)=\Theta_{q,r}\left(\frac{q^n}{n^{\lfloor r/2\rfloor}}\right)

holds for every fixed q≥3q\ge3 and r≥1r\ge1. Theorem 1.3 confirms this at distances one and two, whereas Theorem 1.5 disproves it already for q=r=3q=r=3. The fixed even-distance question remains open in general and motivates Conjecture 1.7.

At distance three we use two different constructions. For an arbitrary fixed alphabet, we construct coordinate weights avoiding all three-term relations with nonzero coefficients in {±1,…,±(q−1)}\{\pm1,\ldots,\pm(q-1)\}. Their weighted sum gives a proper coloring of Hq(n,3)H_q(n,3) and hence a large independent set. For the ternary alphabet, a quadratic construction based on zero-sum Ramsey labelings yields substantially larger triangle-free sets.

Theorem 1.4 (Avoiding distance 3). For every fixed integer q≥2q\ge2,

α(Hq(n,3))≥qnnexp⁡(Oq(log⁡n)).\alpha(H_q(n,3))\ge\frac{q^n}{n\exp(O_q(\sqrt{\log n}))}.

In particular,

Tq(n,3)≥qnn−1−o(1).T_q(n,3)\ge q^n n^{-1-o(1)}.

All logarithms without an indicated base are natural. During the preparation of this manuscript, we became aware of Yekhanin’s recent work [20], which gives a general construction of large codes for every fixed minimum Hamming distance at least four. The numerical bound in Theorem 1.4 can be derived from his distance-four case. Our construction using relation-avoiding weights was obtained independently, before the appearance of his preprint. We present it here in the exact-distance graph setting, where it provides a comparison with the larger triangle-free sets obtained by our ternary Ramsey construction.

Theorem 1.4 deliberately forbids every distance-three edge. For the ternary alphabet, we can obtain a substantially stronger bound by forbidding triangles only. The reason is that the type a=0a=0 is an affine line

x,x+u,x−u,wt⁡(u)=3,x,\quad x+u,\quad x-u,\qquad\operatorname{wt}(u)=3,

whereas the type a=1a=1 can be separated by a linear statistic. A quadratic statistic built from a zero-sum-free labeling of the edges of a complete graph then eliminates the remaining affine-line triangles.

To state the result, let us recall that a cap set in F3m\mathbb{F}_3^m is a vertex set which does not contain 3 collinear points. Let M(m)M(m) be the maximum size of a cap in F3m\mathbb{F}_3^m and put

κ3=lim⁡m→∞M(m)1/m,α=log⁡3κ3.(2)\kappa_3=\lim_{m\to\infty}M(m)^{1/m},\qquad\alpha=\log_3\kappa_3. \tag*{(2)}

The limit exists because Cartesian products of caps give M(m+ℓ)≥M(m)M(ℓ)M(m+\ell)\ge M(m)M(\ell).

Theorem 1.5 (Ternary case, distance r=3r=3). As n→∞n\to\infty,

T3(n,3)≥(α27−o(1))log⁡log⁡nlog⁡n3n.T_3(n,3)\ge\left(\frac{\alpha}{27}-o(1)\right)\frac{\log\log n}{\log n}3^n.

Along an infinite sequence of dimensions,

T3(n,3)≥(α9−o(1))log⁡log⁡nlog⁡n3n.T_3(n,3)\ge\left(\frac{\alpha}{9}-o(1)\right)\frac{\log\log n}{\log n}3^n.

For q=3q=3, this improves the lower bound supplied by Theorem 1.4 to a density of order log⁡log⁡n/log⁡n\log\log n/\log n. The improvement comes from controlling triangles directly, while allowing edges within each class.

In the opposite direction, Proposition 2.6 gives an explicit constant-density upper bound for every fixed q≥3q\ge3. In particular, we prove that

T3(n,3)≤(527+O(n−1))3n.T_3(n,3)\le\left(\frac{5}{27}+O(n^{-1})\right)3^n.

Whether this density tends to zero remains open.

For every prime power qq, the extended BCH construction in Proposition 3.1 gives

Tq(n,r)=Ωq,r(qnn⌊(q−1)r/q⌋)(r≥2 fixed).T_q(n,r)=\Omega_{q,r}\left(\frac{q^n}{n^{\lfloor(q-1)r/q\rfloor}}\right)\qquad(r\ge2\text{ fixed}).

At q=3q=3 and r=4r=4, it matches Proposition 1.2 and yields the following exact order.

Theorem 1.6 (Ternary case, distance r=4r=4).

T3(n,4)=Θ(3nn2).T_3(n,4)=\Theta\left(\frac{3^n}{n^2}\right).

Theorems 1.3 and 1.6 suggest that the binary-subcube upper bound may give the correct power of nn at every fixed even distance. The general sparse hypergraph bound in Theorem 2.5 gives Ωq,h(qnlog⁡n/n3h/2)\Omega_{q,h}(q^n\sqrt{\log n}/n^{3h/2}) for q≥3q\ge3. The BCH construction improves the polynomial exponent in some cases, but the even-distance upper bound is not matched in general.

Conjecture 1.7 (Fixed even distances). For every fixed q≥2q \ge2 and h≥1h \ge1,

Tq(n,2h)=Θq,h(qnnh)T_q(n,2h)=\Theta_{q,h}\left(\frac{q^n}{n^h}\right)

The central open case is nevertheless the odd-distance ternary problem. Even for T3(n,3)T_3(n,3), there is no vanishing-density upper bound matching Theorem 1.5. For odd r≥5r \ge5, the local classification introduces several exceptional-coordinate types simultaneously, and neither binary restriction nor a single quadratic statistic controls them all. Understanding how to combine higher-order algebraic labels with these local types appears to be the main structural obstacle.

The paper is organized as follows. § 2 establishes the local classification, the averaging principles, the sparse hypergraph lower bound, and the counting upper bound at distance three. § 3 settles distances one and two and presents the prime-power BCH construction, with ternary distance four as a corollary. § 4 gives the distance-three construction using relation-avoiding weights, and § 5 develops the ternary Ramsey construction. Finally, § 6 discusses the remaining questions and the converse connection to multicolor Ramsey upper bounds.

Preliminaries

Local structure and averaging

We first make precise the coordinatewise description used throughout the paper.

Definition 2.1. We call a coordinate active for a triple of vectors if its three entries are not all equal.

Proposition 2.2 (Local type classification). Suppose that x,y,z∈[q]nx,y,z \in[q]^n satisfy

dH(x,y)=dH(x,z)=dH(y,z)=r.d_{\mathrm{H}}(x,y)=d_{\mathrm{H}}(x,z)=d_{\mathrm{H}}(y,z)=r.

At each active coordinate, either exactly one of x,y,zx,y,z is exceptional and the other two agree, or all three symbols are distinct. If ax,ay,aza_x,a_y,a_z count the three exceptional-coordinate types and dd counts the all-distinct coordinates, then

ax=ay=az=:a,2a+d=r.a_x=a_y=a_z=:a,\qquad2a+d=r.

In particular, 0≤a≤⌊r/2⌋0\le a\le\lfloor r/2\rfloor, d=r−2ad=r-2a, and the active support has size r+ar+a.

Proof. Every active coordinate contributes to exactly two of the three pairwise distances if one symbol is exceptional, and to all three distances if the symbols are pairwise distinct. Consequently

ax+ay+d=r,ax+az+d=r,ay+az+d=r.a_x+a_y+d=r,\qquad a_x+a_z+d=r,\qquad a_y+a_z+d=r.

Subtracting these equations gives ax=ay=az=aa_x=a_y=a_z=a, after which 2a+d=r2a+d=r. The support calculation is ax+ay+az+d=3a+d=r+aa_x+a_y+a_z+d=3a+d=r+a.

In the binary cube an all-distinct coordinate is impossible, so Proposition 2.2 forces d=0d=0 and r=2ar=2a. This recovers the familiar parity obstruction to binary equilateral triangles. If q≥3q\ge3, every admissible pair (a,d)(a,d) satisfying r+a≤nr+a\le n is realizable.

We next give the two averaging arguments used to transfer bounds. Although elementary, they are especially useful because they preserve density exactly.

Lemma 2.3 (Coordinate-face averaging). If n≥k≥rn \ge k \ge r, then

Tq(n,r)qn≤Tq(k,r)qk.\frac{T_q(n,r)}{q^n} \le\frac{T_q(k,r)}{q^k}.

Proof. Let A⊆[q]nA \subseteq[q]^n be triangle-free. Choose kk coordinates to remain free and assign symbols independently and uniformly to the other n−kn-k coordinates. The resulting face is an isometric copy of [q]k[q]^k, and each element of AA belongs to it with probability q−(n−k)q^{-(n-k)}. Hence the expected size of the intersection is ∣A∣q−(n−k)|A|q^{-(n-k)}. Every such intersection is triangle-free in Hq(k,r)H_q(k,r), so ∣A∣q−(n−k)≤Tq(k,r)|A|q^{-(n-k)} \le T_q(k,r).

Lemma 2.4 (Alphabet restriction). If 2≤p≤q2 \le p \le q, then

Tq(n,r)qn≤Tp(n,r)pn,equivalentlyTq(n,r)≤(qp)nTp(n,r).\frac{T_q(n,r)}{q^n} \le\frac{T_p(n,r)}{p^n}, \qquad\text{equivalently} \qquad T_q(n,r) \le\left(\frac{q}{p}\right)^n T_p(n,r).

Proof. In each coordinate choose a uniformly random pp-element subset of the qq-symbol alphabet, independently of the other coordinates. Their product is an isometric copy of [p]n[p]^n. A fixed word lies in this copy with probability (p/q)n(p/q)^n. Thus, for every triangle-free A⊆[q]nA \subseteq[q]^n, the expected size of its intersection with the random copy is (p/q)n∣A∣(p/q)^n|A|. Every intersection has size at most Tp(n,r)T_p(n,r), proving the result.

Restriction-and-averaging arguments of this kind also occur in the literature on perfect hashing and trifferent codes. Bhandari and Khetan average translates of a code against fixed symbol-weight layers, and note the corresponding formulation for an arbitrary test set [4 Lemma 1.3 and Remark 1.4]. Bishnoi, Kielak, Kovács, Nagy, Somlai, Vizer, and Zheng use the resulting translate-density inequality together with coordinate-deletion recurrences in their generalized trifference problem [5 Proposition 1.3 and Lemma 2.5]. These are close variants of the same principle: a global extremal density is compared with the extremal density on a structured family of restrictions.

Taking p=2p=2 and applying (1) proves Proposition 1.2.

A general lower bound from sparse hypergraph coloring

The local classification gives degree and codegree estimates for Hq,n,rH_{q,n,r}. Applying the sparse hypergraph coloring theorem of Cooper and Mubayi [10] then improves the elementary alteration bound by a factor of log⁡n\sqrt{\log n}.

Theorem 2.5 (Sparse hypergraph bound). For fixed q≥3q \ge3 and fixed r≥1r \ge1,

Tq(n,r)=Ωq,r(qnlog⁡nn(r+⌊r/2⌋)/2).T_q(n,r) = \Omega_{q,r}\left(\frac{q^n\sqrt{\log n}}{n^{(r+\lfloor r/2\rfloor)/2}}\right).

For q=2q=2 and fixed even rr, the same argument gives

T2(n,r)=Ωr(2nlog⁡nn3r/4).T_2(n,r) = \Omega_r\left(\frac{2^n\sqrt{\log n}}{n^{3r/4}}\right).

Proof. Fix x∈[q]nx \in[q]^n and a local type aa, and put d=r−2ad=r-2a. To construct an ordered pair (y,z)(y,z) of this type, choose disjoint coordinate sets of sizes a,a,a,da,a,a,d for the three exceptional types and the all-distinct type. There are q−1q-1 choices at each exceptional coordinate and (q−1)(q−2)(q-1)(q-2) choices at each all-distinct coordinate. Thus the number of ordered pairs is

(nr+a)(a!)3d!(q−1)r+a(q−2)d,(3)\frac{\binom{n}{r+a}}{(a!)^3d!}(q-1)^{r+a}(q-2)^d, \tag*{(3)}

where (nm)=n(n−1)⋯(n−m+1)\binom{n}{m}=n(n-1)\cdots(n-m+1). Let H=Hq,n,r\mathcal{H}=\mathcal{H}_{q,n,r} and put h=⌊r/2⌋h=\lfloor r/2\rfloor. For fixed q≥3q\ge3 and rr, summing (3) over 0≤a≤h0\le a\le h and dividing by two gives

Δ:=Δ(H)=Θq,r(nr+h).\Delta:=\Delta(\mathcal{H})=\Theta_{q,r}(n^{r+h}).

The maximum pair codegree Δ2(H)\Delta_2(\mathcal{H}) is the largest number of hyperedges containing a fixed pair of distinct vertices. A pair not at distance rr has codegree zero. Fix x,yx,y with dH(x,y)=rd_{\mathcal{H}}(x,y)=r, and let S={i:xi≠yi}S=\{i:x_i\ne y_i\}, so ∣S∣=r|S|=r. For a common distance-rr neighbour zz, let aa count the coordinates outside SS at which zz differs from the common value of x,yx,y. Within SS, let b,c,db,c,d count, respectively, the coordinates where z=xz=x, where z=yz=y, and where zz differs from both. The distance equations are

b+c+d=r,a+c+d=r,a+b+d=r.b+c+d=r,\qquad a+c+d=r,\qquad a+b+d=r.

Hence b=c=ab=c=a and d=r−2ad=r-2a, so the codegree of {x,y}\{x,y\} is

∑a=0min⁡{h,n−r}(n−ra)(q−1)ar!(a!)2(r−2a)!(q−2)r−2a=Oq,r(nh).(4)\sum_{a=0}^{\min\{h,n-r\}}\binom{n-r}{a}(q-1)^a\frac{r!}{(a!)^2(r-2a)!}(q-2)^{r-2a}=O_{q,r}(n^h). \tag*{(4)}

The 3-uniform case of the theorem of Cooper and Mubayi [10] states that a hypergraph of maximum degree Δ\Delta and maximum pair codegree at most Δ1/2/f\Delta^{1/2}/f has chromatic number O(Δ/log⁡f)O(\sqrt{\Delta}/\log f) for sufficiently large ff. Here Δ1/2/nh=Θq,r(n(r−h)/2)\Delta^{1/2}/n^h=\Theta_{q,r}(n^{(r-h)/2}), so we may take f=n(r−h)/4f=n^{(r-h)/4} for all sufficiently large nn. Since $r-h>0,

χ(H)=Oq,r(n(r+h)/2log⁡n).\chi(\mathcal{H})=O_{q,r}\left(\frac{n^{(r+h)/2}}{\sqrt{\log n}}\right).

Each color class is independent in H\mathcal{H} and thus induces a triangle-free subgraph of Hq(n,r)H_q(n,r). A largest class has size at least qn/χ(H)q^n/\chi(\mathcal{H}), proving the first assertion.

When q=2q=2 and rr is even, only the type a=r/2a=r/2, d=0d=0 survives. Then Δ=Θr(n3r/2)\Delta=\Theta_r(n^{3r/2}), and a distance-rr pair has codegree

(n−rr/2)r!((r/2)!)2=Or(nr/2).\binom{n-r}{r/2}\frac{r!}{((r/2)!)^2}=O_r(n^{r/2}).

Taking f=nr/8f=n^{r/8} proves the binary assertion, which remains weaker than the sharp bound (1).

For comparison, elementary alteration uses only the vertex-degree estimate. With h=⌊r/2⌋h=\lfloor r/2\rfloor, selecting vertices with probability p=cq,rn−(r+h)/2p=c_{q,r}n^{-(r+h)/2} gives pqnp q^n expected selected vertices and Oq,r(p3qnnr+h)O_{q,r}(p^3q^n n^{r+h}) expected selected triangles. For sufficiently small cq,r>0c_{q,r}>0, deleting one vertex from each surviving triangle gives Ωq,r(qn/n(r+h)/2)\Omega_{q,r}(q^n/n^{(r+h)/2}) vertices. The codegree estimate supplies the additional factor log⁡n\sqrt{\log n}. For odd rr, the polynomial exponent is (3r−1)/4(3r-1)/4; for r=2hr=2h it is 3h/2=3r/43h/2=3r/4.

An upper bound at distance three

Proposition 2.6. For every fixed integer q≥3q\ge3,

Tq(n,3)≤(1+4(q−1)3/(max⁡{q,9}−1)q(2q−3)2+Oq(n−1))qn.T_q(n,3)\le\left(\frac{1+4(q-1)^3/(\max\{q,9\}-1)}{q(2q-3)^2}+O_q(n^{-1})\right)q^n.

For the ternary alphabet, the following explicit bound holds:

T3(n,3)≤5n−127(n−1)3n=(527+427(n−1))3n(n≥5).T_3(n,3)\le\frac{5n-1}{27(n-1)}3^n=\left(\frac{5}{27}+\frac{4}{27(n-1)}\right)3^n\qquad(n\ge5).

Proof. Let A⊆[q]nA \subseteq[q]^n be nonempty and triangle-free in Hq(n,3)H_q(n,3), and let ej(A)e_j(A) count its unordered pairs at distance jj. For n≥4n \ge4, the graph contains both the qq-clique {(u,u,u,0,…,0):u∈[q]}\{(u,u,u,0,\ldots,0):u\in[q]\} and the 99-clique {(u,v,u+v,u−v,0,…,0):u,v∈F3}\{(u,v,u+v,u-v,0,\ldots,0):u,v\in\mathbb{F}_3\}, embedded into three alphabet symbols. Averaging isometric copies of the larger clique through any x∈Ax\in A gives

2e3(A)≤(q−1)3(n3)max⁡{q,9}−1∣A∣.(5)2e_3(A) \le\frac{(q-1)^3\binom{n}{3}}{\max\{q,9\}-1}|A|. \tag*{(5)}

Indeed, each copy contains at most one further point of AA, and the isometries fixing xx act transitively on its distance-three neighbours.

For each coordinate line ℓ\ell, obtained by fixing all but one coordinate, let sℓs_\ell count the points of AA on ℓ\ell, and let tℓt_\ell count those at distance one from ℓ\ell. There are nqn−1nq^{n-1} such lines, and

∑ℓsℓ=n∣A∣,∑ℓtℓ=n(n−1)(q−1)∣A∣.\sum_{\ell}s_\ell=n|A|,\qquad\sum_{\ell}t_\ell=n(n-1)(q-1)|A|.

Counting pairs according to their distance gives

∑ℓsℓ2=n∣A∣+2e1(A),\sum_{\ell}s_\ell^2=n|A|+2e_1(A),
∑ℓsℓtℓ=2(n−1)e1(A)+4e2(A),\sum_{\ell}s_\ell t_\ell=2(n-1)e_1(A)+4e_2(A),
∑ℓtℓ2=n(n−1)(q−1)∣A∣+2(n−1)(2q−3)e1(A)+4(n+q−4)e2(A)+12e3(A).\sum_{\ell}t_\ell^2=n(n-1)(q-1)|A|+2(n-1)(2q-3)e_1(A) +4(n+q-4)e_2(A)+12e_3(A).

In particular, two points at distance three have exactly six coordinate lines at distance one from both: choose one of their three differing coordinates as the line direction, then one of two assignments on the remaining differing coordinates.

Expanding the square below cancels the e2(A)e_2(A) term and gives the coefficient −3n2/2+Oq(n)-3n^2/2+O_q(n) for e1(A)e_1(A). Thus, for sufficiently large nn, (5) yields

∑ℓ(tℓ−n+q−42sℓ)2≤[(14+(q−1)3max⁡{q,9}−1)n3+Oq(n2)]∣A∣.(6)\sum_{\ell}\left(t_\ell-\frac{n+q-4}{2}s_\ell\right)^2 \le\left[\left(\frac{1}{4}+\frac{(q-1)^3}{\max\{q,9\}-1}\right)n^3+O_q(n^2)\right]|A|. \tag*{(6)}

On the other hand, Cauchy–Schwarz and the first-moment identities give

∑ℓ(tℓ−n+q−42sℓ)2≥n((n−1)(q−1)−(n+q−4)/2)2qn−1∣A∣2=(q(2q−3)24n3+Oq(n2))∣A∣2qn.\begin{aligned} \sum_{\ell}\left(t_\ell-\frac{n+q-4}{2}s_\ell\right)^2 \ge\frac{n\left((n-1)(q-1)-(n+q-4)/2\right)^2}{q^{n-1}}|A|^2 \\ &= \left(\frac{q(2q-3)^2}{4}n^3+O_q(n^2)\right)\frac{|A|^2}{q^n}. \end{aligned}

Combining this with (6) proves the general bound. For q=3q=3, the same calculation gives an explicit bound. Indeed, the exact moment identities yield

∑ℓ(tℓ−n−12sℓ)2=n(n−1)(n+7)4∣A∣+32(n−1)(5−n)e1(A)+12e3(A).\sum_{\ell}\left(t_\ell-\frac{n-1}{2}s_\ell\right)^2 =\frac{n(n-1)(n+7)}{4}|A|+\frac{3}{2}(n-1)(5-n)e_1(A)+12e_3(A).

For n≥5n \ge5, the coefficient of e1(A)e_1(A) is nonpositive, while (5) gives

12e3(A)≤n(n−1)(n−2)∣A∣.12e_3(A) \le n(n-1)(n-2)|A|.

Consequently, Cauchy–Schwarz and the first-moment identities give

27n(n−1)24∣A∣23n≤∑ℓ(tℓ−n−12sℓ)2≤n(n−1)(5n−1)4∣A∣.\frac{27n(n-1)^2}{4}\frac{|A|^2}{3^n} \le\sum_{\ell}\left(t_\ell-\frac{n-1}{2}s_\ell\right)^2 \le\frac{n(n-1)(5n-1)}{4}|A|.

Dividing proves the explicit ternary bound.

The clique input above is optimal: the classification of equidistant distance-three codes by Bogdanova and Katona [6 Theorem 2.4] implies

ω(Hq(n,3))=max⁡{q,9}(q≥3, n≥4).\omega(H_q(n,3))=\max\{q,9\}\qquad(q\ge3,\ n\ge4).

Our proof uses only the explicit cliques, but their maximality shows that the clique-averaging estimate (5) cannot be strengthened by choosing a larger clique.

Small distances and BCH constructions

The cases r=1r=1 and r=2r=2

We start by proving Theorem 1.3. At unit distance, the answer comes from the geometry of coordinate lines.

Proof of Theorem 1.3 for r=1r=1. Fix a coordinate ii and all entries outside that coordinate. The resulting coordinate line is a copy of KqK_q in Hq(n,1)H_q(n,1), and a triangle-free set contains at most two of its points. The qn−1q^{n-1} parallel coordinate lines partition the cube, so Tq(n,1)≤2qn−1T_q(n,1)\le2q^{n-1}.

For the reverse inequality, identify the alphabet with Zq\mathbb{Z}_q and take

A={x∈(Zq)n:∑i=1nxi∈{0,1}}.A=\left\{x\in(\mathbb{Z}_q)^n:\sum_{i=1}^{n}x_i\in\{0,1\}\right\}.

Every coordinate line meets AA in exactly two points. Hence AA is triangle-free and ∣A∣=2qn−1|A|=2q^{n-1}.

At distance two we use a checksum whose coefficients avoid all bounded two-term relations. The construction works over any alphabet and produces an independent set.

Proof of Theorem 1.3 for r=2r=2. Let Dq={±1,…,±(q−1)}D_q=\{\pm1,\ldots,\pm(q-1)\}. Choose a prime p=Θq(n)p=\Theta_q(n), with the implicit constant sufficiently large. On Fp\mathbb{F}_p, join distinct u,vu,v whenever

c1u+c2v=0c_1u+c_2v=0

for some c1,c2∈Dqc_1,c_2\in D_q.

This graph has maximum degree Oq(1)O_q(1), because u/vu/v belongs to the fixed set {−c2/c1:c1,c2∈Dq}\{-c_2/c_1:c_1,c_2\in D_q\}. It therefore has an independent set of order Ωq(p)\Omega_q(p); our choice of the implicit constant allows us to select distinct elements w1,…,wnw_1,\ldots,w_n from it.

Label the alphabet by 0,1,…,q−10,1,\ldots,q-1 and color x∈[q]nx\in[q]^n by

χ(x)=∑i=1nwixi(modp).\chi(x)=\sum_{i=1}^{n}w_ix_i\pmod p.

If equally colored words differed in exactly two coordinates i,ji,j, then c1wi+c2wj=0c_1w_i+c_2w_j=0 for some c1,c2∈Dqc_1,c_2\in D_q, contrary to the choice of the weights. Thus every color class is independent in Hq(n,2)H_q(n,2). There are p=Oq(n)p=O_q(n) classes, so the largest has size Ωq(qn/n)\Omega_q(q^n/n). The matching upper bound follows from Proposition 1.2 with h=1h=1.

Extended BCH constructions over prime-power alphabets

The following construction uses the standard parity-check equations for extended Bose–Chaudhuri–Hocquenghem (BCH) codes, see also [21] for the fixed-distance coding context. We include the argument to record its consequences for triangle-free induced subgraphs at every fixed distance over a prime-power alphabet. A Vandermonde system excludes differences of small weight, while the Frobenius identity reduces the number of moments that must be recorded.

Proposition 3.1 (Prime-power BCH construction). Let q≥2q \ge2 be a prime power and let n≥r≥2n \ge r \ge2 be integers. Put

e=⌊(q−1)rq⌋.e = \left\lfloor\frac{(q-1)r}{q} \right\rfloor.

There is a proper coloring of Hq(n,r)H_q(n,r) with fewer than qe+1neq^{e+1}n^e colors whose nonempty color classes have minimum Hamming distance at least r+1r+1. Consequently,

Tq(n,r)>2qe+1qnne.(7)T_q(n,r) > \frac{2}{q^{e+1}}\frac{q^n}{n^e}. \tag*{(7)}

Proof. Let qmq^m be the smallest power of qq at least nn, and set K=FqmK = \mathbb{F}_{q^m}. Thus n≤∣K∣<qnn \le|K| < qn. Choose distinct elements a1,…,an∈Ka_1,\ldots,a_n \in K, and put

J={j∈{1,…,r−1}:q∤j}.J = \{j \in\{1,\ldots,r-1\}: q \nmid j\}.

Then

∣J∣=r−1−⌊r−1q⌋=⌊(q−1)rq⌋=e.|J| = r-1-\left\lfloor\frac{r-1}{q}\right\rfloor = \left\lfloor\frac{(q-1)r}{q}\right\rfloor= e.

Identify the alphabet with Fq\mathbb{F}_q. For x∈Fqnx \in\mathbb{F}_q^n, write

S0(x)=∑i=1nxi∈Fq,Sj(x)=∑i=1naijxi∈K(j≥1),S_0(x) = \sum_{i=1}^{n} x_i \in\mathbb{F}_q,\qquad S_j(x) = \sum_{i=1}^{n} a_i^j x_i \in K \quad(j \ge1),

and color xx by

Φ(x)=(S0(x),(Sj(x))j∈J)∈Fq×KJ.\Phi(x) = \left(S_0(x),(S_j(x))_{j\in J}\right) \in\mathbb{F}_q \times K^J.

Suppose distinct vertices x,yx,y have the same color, and put u=x−yu=x-y. Since ui∈Fqu_i \in\mathbb{F}_q, the Frobenius identity gives Sqj(u)=Sj(u)qS_{qj}(u)=S_j(u)^q for every j≥1j \ge1. Every positive integer at most r−1r-1 is qjq^j for some j∈Jj \in J, so equality of colors implies

Sj(u)=0(0≤j≤r−1).S_j(u)=0 \qquad(0 \le j \le r-1).

If w=wt⁡(u)≤rw=\operatorname{wt}(u)\le r and supp⁡(u)={i1,…,iw}\operatorname{supp}(u)=\{i_1,\ldots,i_w\}, the first ww equations are

∑ℓ=1waiℓjuiℓ=0(0≤j≤w−1),\sum_{\ell=1}^{w} a_{i_\ell}^{j}u_{i_\ell}=0 \qquad(0 \le j \le w-1),

with all coefficients equal to one in the equation for j=0j=0. Their Vandermonde determinant is ∏s<t(ait−ais)≠0\prod_{s<t}(a_{i_t}-a_{i_s})\ne0, forcing u=0u=0, a contradiction. Every nonempty fiber therefore has minimum distance at least r+1r+1.

There are at most q∣K∣e<qe+1neq|K|^e < q^{e+1}n^e colors. The map Φ\Phi is Fq\mathbb{F}_q-linear, so its nonempty fibers have equal size, at least qn/(q∣K∣e)q^n/(q|K|^e). Its first coordinate is surjective, so there are at least q≥2q \ge2 nonempty fibers. The union of two distinct fibers induces a bipartite graph and has size at least

2qnq∣K∣e>2qe+1qnne,\frac{2q^n}{q|K|^e} > \frac{2}{q^{e+1}}\frac{q^n}{n^e},

which proves (7). ∎

If nn is a power of qq, taking ∣K∣=n|K| = n improves the constant to Tq(n,r)≥2qn/(qne)T_q(n,r) \ge2q^n/(q n^e). At ternary distance four the construction matches the binary-subcube upper bound, proving Theorem 1.6.

Corollary 3.2 (Ternary distance four). As n→∞n \to\infty,

T3(n,4)=Θ(3nn2).T_3(n,4) = \Theta\left(\frac{3^n}{n^2}\right).

Proof. Taking q=3q = 3 and r=4r = 4 in Proposition 3.1 gives T3(n,4)>2⋅3n/(27n2)T_3(n,4) > 2 \cdot3^n/(27n^2) for n≥4n \ge4. The matching upper bound follows from Proposition 1.2.

Excluding a fixed clique

The averaging and coloring arguments also apply when a larger fixed clique is forbidden.

Corollary 3.3. For every fixed h≥1h \ge1, s≥2s \ge2, and integer q≥2q \ge2,

αs(Hq(n,2h))=Oh,s(qnnh).\alpha_s(H_q(n,2h)) = O_{h,s}\left(\frac{q^n}{n^h}\right).

For every fixed s≥2s \ge2 and q≥2q \ge2,

αs(Hq(n,2))=Θq,s(qnn),αs(H3(n,4))=Θs(3nn2).\alpha_s(H_q(n,2)) = \Theta_{q,s}\left(\frac{q^n}{n}\right), \qquad\alpha_s(H_3(n,4)) = \Theta_s\left(\frac{3^n}{n^2}\right).

More generally, for every fixed prime power qq and fixed r,s≥2r,s \ge2,

αs(Hq(n,r))=Ωq,r,s(qnn⌊(q−1)r/q⌋).\alpha_s(H_q(n,r)) = \Omega_{q,r,s}\left(\frac{q^n}{n^{\lfloor(q-1)r/q \rfloor}}\right).

Proof. Let A⊆[q]nA \subseteq[q]^n induce a KsK_s-free subgraph of Hq(n,2h)H_q(n,2h). Intersecting AA with a uniformly random coordinatewise binary subcube and taking expectations gives

(2q)n∣A∣≤αs(H2(n,2h)).\left(\frac{2}{q}\right)^n |A| \le\alpha_s(H_2(n,2h)).

The upper bound follows from (1). For the lower bounds, the union of at most s−1s-1 classes of a proper coloring is KsK_s-free. The distance-two checksum uses Oq(n)O_q(n) colors, and Proposition 3.1 uses Oq,r(n⌊(q−1)r/q⌋)O_{q,r}(n^{\lfloor(q-1)r/q \rfloor}) colors. Taking their largest classes proves the lower bounds. For q=3q = 3 and r=4r = 4, the latter exponent is two, matching the upper bound.

Distance r=3r = 3, qq-ary construction

We prove Theorem 1.4 by constructing coordinate weights with no bounded-coefficient relation involving three distinct indices. The main ingredient is the limited-ratio-free set construction of Erdős, Frankl, and Rödl [12], in the formulation of Theorem 2.5 of [14]; Alon and Shapira [1] developed a more general framework for avoiding systems of linear equations. A translation eliminates relations whose coefficients have nonzero sum, and a suitable modulus preserves the resulting avoidance property. The weighted coordinate sum then gives a proper coloring of Hq(n,3)H_q(n,3).

Theorem 4.1 (Alon–Shapira, limited-ratio form). For every fixed positive integer hh, there is a constant ch>0c_h > 0 such that for every N≥2N \ge2 there is a set B⊆{1,…,N}B \subseteq\{1,\ldots,N\} satisfying

∣B∣≥Nexp⁡(−chlog⁡N)|B| \ge N\exp(-c_h\sqrt{\log N})

and containing no three distinct elements a,b,ca,b,c for which

λa+μb=(λ+μ)c(1≤λ,μ≤h).\lambda a+\mu b=(\lambda+\mu)c \qquad(1\le\lambda,\mu\le h).

Lemma 4.2 (Coefficient-avoiding weights). Let Dq={±1,…,±(q−1)}D_q=\{\pm1,\ldots,\pm(q-1)\}. For every fixed q≥2q\ge2 there is a constant Cq>0C_q>0 with the following property. For every n≥2n\ge2 one can find an integer

M≤nexp⁡(Cqlog⁡n)M\le n\exp(C_q\sqrt{\log n})

and distinct residues w1,…,wn∈Z/MZw_1,\ldots,w_n\in\mathbb{Z}/M\mathbb{Z} such that

c1wi+c2wj+c3wk≠0(modM)c_1w_i+c_2w_j+c_3w_k\ne0 \pmod M

whenever i,j,ki,j,k are distinct and c1,c2,c3∈Dqc_1,c_2,c_3\in D_q.

Proof. Apply Theorem 4.1 with h=q−1h=q-1. Increasing the implicit constant if necessary, choose

N≤nexp⁡(Cq′log⁡n)N\le n\exp(C'_q\sqrt{\log n})

so that the theorem supplies a limited-ratio-free set B⊆{1,…,N}B\subseteq\{1,\ldots,N\} of size at least nn. Indeed, taking

N=⌈nexp⁡(3cq−1log⁡n)⌉N=\lceil n\exp(3c_{q-1}\sqrt{\log n})\rceil

suffices for all large nn, and the remaining values may be absorbed into the constant.

Set

H=3(q−1)N+1,W=H+B.H=3(q-1)N+1,\qquad W=H+B.

We claim that distinct u,v,w∈Wu,v,w\in W satisfy no integer relation

c1u+c2v+c3w=0,c1,c2,c3∈Dq.(8)c_1u+c_2v+c_3w=0,\qquad c_1,c_2,c_3\in D_q. \tag*{(8)}

Write u=H+au=H+a, v=H+bv=H+b, and w=H+cw=H+c. If c1+c2+c3=0c_1+c_2+c_3=0, then after permuting the variables and multiplying by −1-1 if necessary, (8) has the form

λu+μv=(λ+μ)w,1≤λ,μ≤q−1.\lambda u+\mu v=(\lambda+\mu)w,\qquad1\le\lambda,\mu\le q-1.

The translation by HH cancels and produces a forbidden relation among a,b,c∈Ba,b,c\in B. If instead s:=c1+c2+c3≠0s:=c_1+c_2+c_3\ne0, then

∣sH∣≥Hbut∣c1a+c2b+c3c∣≤3(q−1)N<H,|sH|\ge H\qquad\text{but}\qquad|c_1a+c_2b+c_3c|\le3(q-1)N<H,

which again rules out (8).

Choose nn distinct elements of WW, represented by positive integers, and take M=3(q−1)(H+N)+1M=3(q-1)(H+N)+1. Every relevant three-term sum has absolute value less than MM; congruence to zero modulo MM would therefore imply equality over the integers. The chosen residues have the desired property, and M=Oq(N)≤nexp⁡(Cqlog⁡n)M=O_q(N)\le n\exp(C_q\sqrt{\log n}) after adjusting CqC_q. □

Proof of Theorem 1.4. Take M,w1,…,wnM,w_1,\ldots,w_n from Lemma 4.2 and define

χ:[q]n⟶ZM,χ(x)=∑i=1nwixi(modM).\chi:[q]^n\longrightarrow\mathbb{Z}_M,\qquad\chi(x)=\sum_{i=1}^{n}w_ix_i\pmod M.

If xx and yy differ in exactly the three coordinates i,j,ki,j,k and have the same color, then

(xi−yi)wi+(xj−yj)wj+(xk−yk)wk≡0(modM).(x_i-y_i)w_i+(x_j-y_j)w_j+(x_k-y_k)w_k\equiv0\pmod{M}.

The three coefficients belong to DqD_q, contradicting Lemma 4.2. Hence χ\chi is a proper coloring of Hq(n,3)H_q(n,3). At least one of its at most MM color classes has size at least

qnM≥qnnexp⁡(Cqlog⁡n),\frac{q^n}{M}\geq\frac{q^n}{n\exp(C_q\sqrt{\log n})},

and this class is independent.

The proof gives a proper coloring of Hq(n,3)H_q(n,3), so every color class is independent. In the next section we exploit the greater freedom of requiring the color classes to induce triangle-free subgraphs, using algebraic features specific to the ternary alphabet.

The ternary distance-three problem and Ramsey theory

We now exploit features special to F3\mathbb{F}_3. Proposition 2.2 leaves two types at distance three. For a=0a=0 and d=3d=3, the triangle is an affine line

x,x+u,x−u,wt⁡(u)=3.x,\quad x+u,\quad x-u,\qquad\operatorname{wt}(u)=3.

The second type has (a,d)=(1,1)(a,d)=(1,1). A linear statistic will eliminate the mixed type, while a quadratic statistic will handle the affine lines. Recall the cap-size function M(m)M(m) and the constants κ3\kappa_3 and α\alpha from (2). Cartesian products give M(m+ℓ)≥M(m)M(ℓ)M(m+\ell)\geq M(m)M(\ell), so Fekete’s lemma yields κ3=sup⁡mM(m)1/m\kappa_3=\sup_m M(m)^{1/m} and

M(m)=3m(α+o(1)).(9)M(m)=3^{m(\alpha+o(1))}. \tag*{(9)}

In characteristic three, the cap condition is equivalent to

a+b+c=0,a,b,c∈C,⟹a=b=c.(10)a+b+c=0,\qquad a,b,c\in C,\qquad\Longrightarrow\qquad a=b=c. \tag*{(10)}

Indeed, if two of a,b,ca,b,c agree then all three agree; otherwise the three points are distinct and form an affine line.

The edge-labeling parameter below is an additive analogue of a multicolor Ramsey problem, tailored to the quadratic Hamming lift.

Definition 5.1 (Zero-sum triangle Ramsey number). For an elementary abelian 3-group GG, let Z(G)Z(G) be the largest integer NN for which the edges ij∈E(KN)ij\in E(K_N) of the complete graph KNK_N can be labeled by elements γij∈G\gamma_{ij}\in G so that

γij+γik+γjk≠0(11)\gamma_{ij}+\gamma_{ik}+\gamma_{jk}\ne0 \tag*{(11)}

for every triple of distinct vertices i,j,ki,j,k.

We next derive the required estimate for Z(G)Z(G). This is the key quantitative ingredient in the distance-three lower bound. The argument first packs the group with disjoint cap palettes and then amplifies an ordinary multicolor Ramsey coloring lexicographically.

Lemma 5.2 (Palette amplification). Let GG be an elementary abelian 3-group containing pairwise disjoint caps

P1,…,PL,∣Pj∣=s.P_1,\ldots,P_L,\qquad|P_j|=s.

If the edges of KtK_t admit an ss-coloring with no monochromatic triangles, then

Z(G)≥tL.Z(G)\geq t^L.

Proof. Fix such a coloring φ:E(Kt)→[s]\varphi:E(K_t)\to[s] and bijections ιj:[s]→Pj\iota_j:[s]\to P_j. Use [t]L[t]^L as the vertex set of a complete graph. For distinct u,v∈[t]Lu,v\in[t]^L, let jj be the first coordinate at which they differ and label the edge uvuv by

γ(u,v)=ιj(φ(ujvj))∈Pj.(12)\gamma(u,v)=\iota_j\bigl(\varphi(u_jv_j)\bigr)\in P_j. \tag*{(12)}

Consider three distinct words u,v,wu,v,w, and let jj be the first coordinate at which they are not all equal. If uj,vj,wju_j,v_j,w_j are pairwise distinct, then all three edge labels belong to PjP_j. They are not all equal, since φ\varphi has no monochromatic triangle. By (10), their sum therefore cannot be zero.

Suppose instead that exactly two entries agree, say uj=vj≠wju_j=v_j\ne w_j. The edges uwuw and vwvw receive the same label a∈Pja\in P_j, whereas the edge uvuv is decided at a later coordinate j′>jj'>j and receives a label b∈Pj′b\in P_{j'}. The palettes are disjoint, so a≠ba\ne b; hence, in characteristic three,

a+a+b=b−a≠0.a+a+b=b-a\ne0.

Thus no triangle has label sum zero, proving that Z(G)≥∣[t]L∣=tLZ(G)\ge\lvert[t]^L\rvert=t^L.

It remains to produce sufficiently many disjoint caps. Partitioning F3m\mathbb{F}_3^m into caps is equivalent to properly coloring the affine Steiner triple system AG⁡(m,3)\operatorname{AG}(m,3). The following elementary translate-covering argument is a special case of the general relationship between fractional and integral covers. We include the proof to keep the subsequent construction self-contained.

Lemma 5.3 (Partition into caps). Let C⊆F3mC\subseteq\mathbb{F}_3^m be a cap, put Q=3mQ=3^m, and write M=∣C∣M=\lvert C\rvert. Then F3m\mathbb{F}_3^m can be partitioned into at most

J≤⌈QM(log⁡Q+1)⌉(13)J\le\left\lceil\frac{Q}{M}(\log Q+1)\right\rceil \tag*{(13)}

caps.

Proof. Choose JJ independent uniformly random translates of CC, with JJ equal to the right-hand side of (13). A fixed element of F3m\mathbb{F}_3^m is missed by all the translates with probability

(1−MQ)J≤exp⁡(−JM/Q).\left(1-\frac{M}{Q}\right)^J\le\exp(-JM/Q).

Consequently the expected number of uncovered elements is at most

Qexp⁡(−JM/Q)≤e−1<1.Q\exp(-JM/Q)\le e^{-1}<1.

Some collection of JJ translates therefore covers F3m\mathbb{F}_3^m. Order these translates and assign every element to the first translate containing it. The resulting nonempty parts are pairwise disjoint subsets of translates of CC, hence are caps, and they partition F3m\mathbb{F}_3^m.

Lemma 5.4 (Equal cap palettes). Fix 0<β<α0<\beta<\alpha. For Q=3mQ=3^m and

s=⌊Qβ⌋,s=\lfloor Q^\beta\rfloor,

there are

L=(1−o(1))Qs(14)L=(1-o(1))\frac{Q}{s} \tag*{(14)}

pairwise disjoint caps of size ss, as m→∞m\to\infty.

Proof. Choose β′\beta' with β<β′<α\beta< \beta' < \alpha. From the definition of κ3\kappa_3 and α\alpha we have

M(m)=Qα+o(1),M(m) = Q^{\alpha+o(1)},

so, for all sufficiently large mm, F3m\mathbb{F}_3^m contains a cap of size at least Qβ′Q^{\beta'}. Lemma 5.3 partitions F3m\mathbb{F}_3^m into

J≤Q1−β′+o(1)J \le Q^{1-\beta'+o(1)}

caps. Split every part into sets of size ss, discarding the remainder of each part. Fewer than JsJs elements are discarded, and

Js≤Q1−β′+β+o(1)=o(Q).Js \le Q^{1-\beta'+\beta+o(1)} = o(Q).

The remaining Q−o(Q)Q-o(Q) elements therefore form the asserted family of L=(1−o(1))Q/sL=(1-o(1))Q/s disjoint ss-element caps. □

Let Rs(3)R_s(3) be the least NN such that every ss-coloring of E(KN)E(K_N) contains a monochromatic triangle. We use the following superexponential lower bound from [17 Chapter 9], announced recently by OpenAI.

Theorem 5.5 (Superexponential multicolor Ramsey bound). There is an absolute constant c>0c>0 such that, for every integer s≥2s\ge2,

Rs(3)≥(cs1/3log⁡s)s.(15)R_s(3) \ge\left(\frac{c s^{1/3}}{\log s}\right)^s. \tag*{(15)}

Consequently, as s→∞s\to\infty, there is an ss-coloring of some KtK_t with no monochromatic triangle and

log⁡t≥(13−o(1))slog⁡s.(16)\log t \ge\left(\frac{1}{3}-o(1)\right)s\log s. \tag*{(16)}

This result enables us to prove the zero-sum Ramsey estimate that drives the ternary distance-three construction.

Theorem 5.6 (Zero-sum Ramsey amplification). Let Q=3mQ=3^m. Then

Z(F3m)≥Q(α/3−o(1))Q(m→∞).(17)Z(\mathbb{F}_3^m) \ge Q^{(\alpha/3-o(1))Q} \qquad(m\to\infty). \tag*{(17)}

Proof. Fix 0<β<α0<\beta<\alpha and put s=⌊Qβ⌋s=\lfloor Q^\beta\rfloor. By Lemma 5.4, the group F3m\mathbb{F}_3^m contains

L=(1−o(1))QsL=(1-o(1))\frac{Q}{s}

pairwise disjoint caps of size ss. By Theorem 5.5, there is an ss-coloring of KtK_t with no monochromatic triangle and

log⁡t≥(13−o(1))slog⁡s.\log t \ge\left(\frac{1}{3}-o(1)\right)s\log s.

Lemma 5.2 gives Z(F3m)≥tLZ(\mathbb{F}_3^m)\ge t^L, and hence

log⁡Z(F3m)≥Llog⁡t≥(1−o(1))Qs(13−o(1))slog⁡s=(β3−o(1))Qlog⁡Q.\begin{aligned} \log Z(\mathbb{F}_3^m) \ge L\log t \\ &\ge(1-o(1))\frac{Q}{s}\left(\frac{1}{3}-o(1)\right)s\log s \\ &= \left(\frac{\beta}{3}-o(1)\right)Q\log Q. \end{aligned}

Thus Z(F3m)≥Q(β/3−o(1))QZ(\mathbb{F}_3^m)\ge Q^{(\beta/3-o(1))Q}. Since β<α\beta<\alpha is arbitrary, (17) follows. □

Corollary 5.7. As m→∞m \to\infty, log⁡Z(F3m)=Θ(m3m)\log Z(\mathbb{F}_3^m) = \Theta(m3^m). More precisely, writing Q=3mQ = 3^m, we have Q(α/3−o(1))Q≤Z(F3m)≤Q(1+o(1))QQ^{(\alpha/3-o(1))Q} \le Z(\mathbb{F}_3^m) \le Q^{(1+o(1))Q}.

Proof. The lower bound is Theorem 5.6. A labeling by F3m\mathbb{F}_3^m can be regarded as an edge-coloring with QQ colors. Every monochromatic triangle has label sum zero, so Z(F3m)<RQ(3)Z(\mathbb{F}_3^m) < R_Q(3). The classical factorial upper bound RQ(3)=O(Q!)R_Q(3) = O(Q!) gives the required upper estimate.

Theorem 5.8 (Zero-sum Ramsey input). Let κ3\kappa_3 and α\alpha be defined by (2). For every sufficiently large nn there is an elementary abelian 3-group GG with n≤Z(G)n \le Z(G) and

∣G∣≤(9α+o(1))log⁡nlog⁡log⁡n.|G| \le\left(\frac{9}{\alpha}+o(1)\right)\frac{\log n}{\log\log n}.

Along an infinite sequence of values of nn, one may replace 9/α9/\alpha by 3/α3/\alpha.

Proof. Fix 0<η<α/30 < \eta< \alpha/3. Theorem 5.6 implies that for every sufficiently large power Q=3mQ = 3^m,

Z(F3m)≥QηQ.(18)Z(\mathbb{F}_3^m) \ge Q^{\eta Q}. \tag*{(18)}

Given a sufficiently large nn, choose the least power of three QQ for which

n≤QηQ.n \le Q^{\eta Q}.

Then (18) supplies the required labeling in G=F3mG = \mathbb{F}_3^m. By the minimality of QQ, the preceding power Q/3Q/3 satisfies

n>(Q3)ηQ/3,n > \left(\frac{Q}{3}\right)^{\eta Q/3},

and therefore

log⁡n>ηQ3log⁡Q3.(19)\log n > \frac{\eta Q}{3}\log\frac{Q}{3}. \tag*{(19)}

Together with log⁡n≤ηQlog⁡Q\log n \le\eta Q\log Q, this shows that

Q=Θ(log⁡nlog⁡log⁡n)andlog⁡Q=(1+o(1))log⁡log⁡n.Q = \Theta\left(\frac{\log n}{\log\log n}\right) \qquad\text{and}\qquad \log Q = (1+o(1))\log\log n.

Substitution in (19) yields

∣G∣=Q≤(3η+o(1))log⁡nlog⁡log⁡n.|G| = Q \le\left(\frac{3}{\eta}+o(1)\right)\frac{\log n}{\log\log n}.

Letting η\eta tend to α/3\alpha/3 proves the first assertion. For the subsequence assertion, let Q=3mQ = 3^m tend to infinity. From (17) we may choose integers nm≤Z(F3m)n_m \le Z(\mathbb{F}_3^m) satisfying

log⁡nm=(α3−o(1))Qlog⁡Q.\log n_m = \left(\frac{\alpha}{3}-o(1)\right)Q\log Q.

It follows that

Q=(3α+o(1))log⁡nmlog⁡log⁡nm,Q = \left(\frac{3}{\alpha}+o(1)\right)\frac{\log n_m}{\log\log n_m},

which proves the sharper estimate along the infinite sequence (nm)m≥1(n_m)_{m\ge1}.

The available numerical value of κ3\kappa_3 is governed by a succession of explicit constructions. Edel’s generalized product caps yielded the longstanding bound κ3≥2.2174\kappa_3 \ge2.2174 [11]. Tyrrell obtained the first improvement in nearly two decades, reaching 2.2182.218 [19]; the program-search construction of Romera-Paredes et al. subsequently reached 2.22022.2202 [18]. The construction of Zhai et al. [22] gives the explicit lower bound

κ3≥2.2203and henceα≥0.72604.\kappa_3 \ge2.2203 \qquad\text{and hence}\qquad\alpha\ge0.72604.

Consequently the two constants in Theorem 1.5 may presently be taken to be at least

α27≥0.02689,α9≥0.08067,\frac{\alpha}{27} \ge0.02689,\qquad\frac{\alpha}{9} \ge0.08067,

respectively.

The constants in Theorem 1.5 now follow from an explicit coloring. We include the reduction because it exposes the role of the two local types.

Proof of Theorem 1.5. Choose GG and a labeling γij\gamma_{ij} satisfying (11). For x∈F3nx \in\mathbb{F}_3^n define

σ(x)=∑i=1nxi∈F3,Q(x)=∑1≤i<j≤nxixjγij∈G,\sigma(x)=\sum_{i=1}^{n}x_i\in\mathbb{F}_3,\qquad Q(x)=\sum_{1\le i<j\le n}x_ix_j\gamma_{ij}\in G,

and color xx by (σ(x),Q(x))(\sigma(x),Q(x)). This gives at most 3∣G∣3|G| color classes.

Suppose first that x,y,zx,y,z form a triangle of type (a,d)=(1,1)(a,d)=(1,1). Adding the same field element to all three entries in any coordinate shifts their σ\sigma-values equally, so it preserves whether these values coincide. We may therefore normalize every inactive coordinate to zero and the repeated symbol in each exceptional coordinate to zero. The three exceptional coordinates then contribute (ex,0,0)(e_x,0,0), (0,ey,0)(0,e_y,0), and (0,0,ez)(0,0,e_z), respectively, with ex,ey,ez≠0e_x,e_y,e_z\ne0. At the unique all-distinct coordinate, the entries (tx,ty,tz)(t_x,t_y,t_z) form a permutation of F3\mathbb{F}_3. Hence

σ(x)=ex+tx,σ(y)=ey+ty,σ(z)=ez+tz.\sigma(x)=e_x+t_x,\qquad\sigma(y)=e_y+t_y,\qquad\sigma(z)=e_z+t_z.

If these three values were equal to τ\tau, then ex=τ−txe_x=\tau-t_x, ey=τ−tye_y=\tau-t_y, and ez=τ−tze_z=\tau-t_z. Since one of tx,ty,tzt_x,t_y,t_z equals τ\tau, one of ex,ey,eze_x,e_y,e_z would be zero, a contradiction. Thus a mixed triangle is not monochromatic.

It remains to consider a type-(0,3)(0,3) triangle. Write it as x,x+u,x−ux,x+u,x-u, with uu supported on three coordinates i,j,ki,j,k. If the three vertices have the same σ\sigma-value, then ∑iui=0\sum_i u_i=0. Since the three nonzero entries of uu lie in {1,−1}\{1,-1\}, they must all be equal. The quadratic second difference is then

Q(x+u)+Q(x−u)−2Q(x)=2∑a<buaubγab=−(γij+γik+γjk),Q(x+u)+Q(x-u)-2Q(x)=2\sum_{a<b}u_au_b\gamma_{ab}=-(\gamma_{ij}+\gamma_{ik}+\gamma_{jk}),

where the last equality is in characteristic three. This is nonzero by (11). Hence the three QQ-values cannot all agree, and the coloring is triangle-free.

Its largest class has size at least 3n/(3∣G∣)3^n/(3|G|). The first estimate in Theorem 5.8 gives

3n3∣G∣≥(α27−o(1))log⁡log⁡nlog⁡n3n,\frac{3^n}{3|G|}\ge\left(\frac{\alpha}{27}-o(1)\right)\frac{\log\log n}{\log n}3^n,

and the improved estimate along the distinguished subsequence gives the constant α/9\alpha/9.

The construction uses exactly the algebra demanded by the local geometry: the linear coordinate excludes the mixed type and the quadratic coordinate excludes affine lines. In contrast, the proper coloring constructed in Section 4 separates every distance-three pair and is therefore uniform in qq but much less dense when q=3q=3.

Concluding remarks

At odd distances, binary restriction supplies no nontrivial upper bound, since every binary odd-distance graph is bipartite. Over F3\mathbb{F}_3, the type-a=0a=0 triangles are affine lines xx, x+ux+u, x−ux-u with wt⁡(u)=r\operatorname{wt}(u)=r. The essential difficulty is to control these together with all types a≥1a\ge1. At distance three there is only one additional type, and a single linear statistic removes it. For larger odd distances, a replacement may require higher-order labels that encode several exceptional-coordinate patterns at once.

We conclude with three open questions. First, can the lower bounds of Theorem 2.5 and Proposition 3.1 be improved to match the binary-subcube upper bound at every fixed even distance, as proposed in Conjecture 1.7? Second, can the constant-density upper bound of Proposition 2.6 be replaced by a vanishing-density bound? In particular, is T3(n,3)=o(3n)T_3(n,3)=o(3^n), improving the current estimate

T3(n,3)≤(527+O(n−1))3n?T_3(n,3)\le\left(\frac{5}{27}+O(n^{-1})\right)3^n?

Third, can the triangle-free condition be used to improve on the BCH and sparse hypergraph bounds at larger odd distances? The ternary distance-three construction suggests that controlling triangles directly can be substantially more effective than excluding every edge.

There is also a quantitative connection between the upper bounds of T3(n,3)T_3(n,3) and the multicolor triangle Ramsey numbers Rk(3)R_k(3) defined in § 5. Suppose that C⊆F3mC\subseteq\mathbb{F}_3^m is a cap of size at least kk. Thus c1+c2+c3=0c_1+c_2+c_3=0, c1,c2,c3∈Cc_1,c_2,c_3\in C, implies c1=c2=c3c_1=c_2=c_3. Replacing the colors of a kk-edge-coloring without monochromatic triangles by distinct elements of CC therefore produces an edge-labeling without zero-sum triangles. Consequently,

Rk(3)−1≤Z(F3m).R_k(3)-1\le Z(\mathbb{F}_3^m).

The quadratic construction gives the complementary implication

n≤Z(F3m)⟹T3(n,3)≥3n−m−1.n\le Z(\mathbb{F}_3^m)\quad\Longrightarrow\quad T_3(n,3)\ge3^{n-m-1}.

Indeed, the construction partitions the hyperplane {x∈F3n:∑ixi=0}\{x\in\mathbb{F}_3^n:\sum_i x_i=0\} into at most 3m3^m triangle-free fibers, one of which has size at least 3n−m−13^{n-m-1}. Combining these observations yields

T3(n,3)<3n−m−1⟹Rk(3)≤n,(20)T_3(n,3)<3^{n-m-1}\quad\Longrightarrow\quad R_k(3)\le n, \tag*{(20)}

whenever F3m\mathbb{F}_3^m contains a cap of size at least kk. Thus sufficiently strong upper bounds for the distance-three problem would imply upper bounds for classical multicolor triangle Ramsey numbers.

The rate of any decay in T3(n,3)/3nT_3(n,3)/3^n is therefore relevant to Ramsey theory, beyond the qualitative question of whether this density tends to zero. The implications above transfer upper bounds; a positive-density lower bound for T3(n,3)T_3(n,3) alone would not yield a converse Ramsey estimate.

The problem of forbidding larger cliques has already been considered in this setting. Balogh, Chen, and Li [2 Question 1.2 and Theorem 1.4] determined the order of αs(H2(n,r))\alpha_s(H_2(n,r)) for fixed ss and fixed even rr. Mukkamala and Ravi [16 Section 4, Problem 3] explicitly posed the corresponding problem over prime-power alphabets. The constructions above settle the case q=r=3q=r=3 and s=4s=4, as α4(H3(n,3))=3n−1\alpha_4(H_3(n,3))=3^{n-1} for n≥4n\ge4. Indeed, the proof of Theorem 1.5 shows that each fiber of the linear statistic ∑ixi\sum_i x_i contains no triangle of mixed type. Every triangle in such a fiber is therefore an affine line. A K4K_4 is impossible, since its triangles through a fixed edge would have to lie on the same affine line, which contains only three points. Each fiber thus gives a K4K_4-free set of size 3n−13^{n-1}. Conversely, the cosets of the two-dimensional subspace displayed in the proof of Proposition 2.6 partition F3n\mathbb{F}_3^n into 99-cliques. A K4K_4-free set meets each coset in at most three points, proving the matching upper bound. In particular, αs(H3(n,3))≥3n−1\alpha_s(H_3(n,3))\ge3^{n-1} for every s≥4s\ge4, so the question of vanishing density at ternary distance three is specific to the triangle-free problem.

AI declaration. AI-assisted tools were used in editing and preparing the manuscript: during the workshop, the authors used ChatGPT 5.6 Sol, which assisted them in obtaining the main results of the manuscript by building on their ideas. Later, they used ChatGPT 6 Astra for proofreading. The authors reviewed the resulting text and take full responsibility for the mathematical statements, proofs, and references.

Acknowledgement. The problem studied in this paper was posed at the Excellence Workshop, held in Szigliget, Hungary, on 4–9 August 2026. The authors thank the organizers for providing the opportunity for these discussions.

References

  1. [1]N. Alon and A. Shapira, Linear equations, arithmetic progressions and hypergraph property testing, Theory Comput. 1 (2005), 177–216.DOI
  2. [2]J. Balogh, C. Chen, and B. Li, Forbidding exactly one Hamming distance, arXiv:2604.05607, 2026.arxiv.org/abs/2604.05607
  3. [3]L. A. Bassalygo, G. D. Cohen, and G. Zémor, Codes with forbidden distances, Discrete Math. 213 (2000), 3–11. doi:10.1016/S0012-365X(99)00161-2.DOI
  4. [4]S. Bhandari and A. Khetan, Improved upper bound for the size of a trifferent code, Combinatorica 45 (2025), article no. 2, 14 pp. doi:10.1007/s00493-024-00130-2.DOI
  5. [5]A. Bishnoi, B. Kielak, B. Kovács, Z. L. Nagy, G. Somlai, M. Vizer, and Z. Zheng, The generalized trifference problem, IEEE Trans. Inform. Theory 72 (2026), no. 5, 2907–2914. doi:10.1109/TIT.2026.3665439.DOI
  6. [6]G. Bogdanova and G. O. H. Katona, All q-ary equidistant 3-codes, J. Combin. Inform. System Sci. 34 (2009), 161–167.
  7. [7]B. Brešar, N. Gastineau, S. Klavžar, and O. Togni, Exact distance graphs of product graphs, Graphs Combin. 35 (2019), 1555–1569. doi:10.1007/s00373-019-02089-0.DOI
  8. [8]D. Castro-Silva, F. M. de Oliveira Filho, L. Slot, and F. Vallentin, A recursive theta body for hypergraphs, Combinatorica 43 (2023), 909–938.
  9. [9]G. Cohen and G. Zémor, Subset sums and coding theory, Astérisque 258 (1999), 327–339. doi:10.24033/ast.458.
  10. [10]J. Cooper and D. Mubayi, Coloring sparse hypergraphs, SIAM J. Discrete Math. 30 (2016), no. 2, 1165–1180. doi:10.1137/140995805.DOI
  11. [11]Y. Edel, Extensions of generalized product caps, Des. Codes Cryptogr. 31 (2004), 5–14. doi:10.1023/A:1027365901231.DOI
  12. [12]P. Erdős, P. Frankl, and V. Rödl, The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs Combin. 2 (1986), 113–121.DOI
  13. [13]J. R. Johnson and J. Talbot, Vertex Turán problems in the hypercube, J. Combin. Theory Ser. A 117 (2010), no. 4, 454–465. doi:10.1016/j.jcta.2009.07.009.
  14. [14]B. Kovács and Z. L. Nagy, Multicolor Turán numbers II: a generalization of the Ruzsa–Szemerédi theorem and new results on cliques and odd cycles, J. Graph Theory 107 (2024), 629–641.
  15. [15]X.-C. Li and R.-X. Hao, The vertex Turán density in 3-ary n-cubes, Discrete Appl. Math. 311 (2022), 129–141. doi:10.1016/j.dam.2022.01.015.DOI
  16. [16]P. Mukkamala and A. Ravi, Triangle-free subsets of the r-distance graph of the hypercube, arXiv:2506.18782v4, 2026.arxiv.org/abs/2506.18782
  17. [17]OpenAI, Ten Advances in Mathematics and Theoretical Computer Science, Chapter 9, “Super-exponential lower bounds for R(3,…,3),” pp. 229–235, updated 6 August 2026. Available at https://cdn.openai.com/pdf/ten-proofs-oai.pdf.DOI
  18. [18]B. Romera-Paredes, M. Barekatain, A. Novikov, M. Balog, M. P. Kumar, E. Dupont, F. J. R. Ruiz, J. S. Ellenberg, P. Wang, O. Fawzi, P. Kohli, and A. Fawzi, Mathematical discoveries from program search with large language models, Nature 625 (2024), 468–475. doi:10.1038/s41586-023-06924-6.
  19. [19]F. Tyrrell, New lower bounds for cap sets, Discrete Anal. (2023), Paper No. 20, 18 pp. doi:10.19086/da.91076.DOI
  20. [20]S. Yekhanin, Nonlinear fixed-distance codes via real lifts of moment configurations, arXiv:2610.19960, 2026. https://arxiv.org/abs/2610.19960.
  21. [21]S. Yekhanin and I. Dumer, Long nonbinary codes exceeding the Gilbert–Varshamov bound for any fixed distance, IEEE Trans. Inform. Theory 50 (2004), no. 10, 2357–2362. doi:10.1109/TIT.2004.834744.DOI
  22. [22]Y. Zhai, Z. Wei, R. Li, K. Pan, S. Liu, L. Zhang, J. Ji, W. Zhang, Yu Zhang, and Yanyong Zhang, X-evolve: Solution space evolution powered by large language models, arXiv:2508.07932, 2025.arxiv.org/abs/2508.07932

Paper details

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

views · 1

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