Fix an odd cycle C_m, with m=2d+1, and let k_min(C_m) denote the minimum dimension of an isometric embedding of C_m into an abelian Cayley graph. Encode the edge-generator dependencies by the binary code D=Biglx∈F_2^m: ∑_i:x_i=1s_i=0 Bigr. The code contains the all-ones vector, and for every cyclic interval W⊆Z_m isometry requires min_x∈ D|W triangle x|=min bigl(|W|,m-|W|bigr). Odd-cycle naive-dimension conjecture. The cyclic interval lemma holds for every odd m; consequently, k_min(C_m)=m-1 for every odd cycle. The claim is proved in the paper for every odd m≤17 and for any further odd m for which the cyclic interval lemma holds; the general case remains open.

The odd-cycle naive-dimension conjecture

Less than 1 year old · traced to 2026

Fix an odd cycle $C_m$ , with $m=2d+1$ , and let $k_{\min}(C_m)$ denote the minimum dimension of an isometric embedding of $C_m$ into an abelian Cayley graph. Encode the edge-generator dependencies by the binary code

D=\Bigl\{x\in\mathbb{F}_2^m:\ \sum_{i:x_i=1}s_i=0\Bigr\}.

The code contains the all-ones vector, and for every cyclic interval $W\subseteq\mathbb{Z}_m$ isometry requires

\min_{x\in D}|W\triangle x|=\min\bigl(|W|,m-|W|\bigr).

Odd-cycle naive-dimension conjecture. The cyclic interval lemma holds for every odd $m$ ; consequently,

k_{\min}(C_m)=m-1

for every odd cycle. The claim is proved in the paper for every odd $m\leq17$ and for any further odd $m$ for which the cyclic interval lemma holds; the general case remains open.

References

Primary source

Fokam Souop Rigobert and Bitjoka Laurent, “Dimension and Order Bounds for Isometric Embeddings of Graphs into Abelian Cayley Graphs, and the Abelian Dividend”, arXiv:2607.07939 (2026).

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed progress

A July 2026 preprint verifies the conjecture only for small odd cycles, while an unverified submission claims a proof for every odd cycle.

The conjecture predicts that the cyclic-interval condition always holds and therefore that $k_{\min}(C_m)=m-1$ for every odd $m$ . Fokam Souop and Bitjoka formulate the reduction in their 2026 preprint.

Known results; July 2026 preprint

Fokam Souop and Bitjoka (2026) prove the dimension formula in the finite checked range, reported as odd $m<17$ .
For any further odd $m$ satisfying the cyclic-interval lemma, their reduction gives $k_{\min}(C_m)=m-1$ .
The preprint does not prove the lemma for all odd $m$ and reports no counterexample or independent verification.

Community submission (unverified)

A submitted proof argues, via averaging over cyclic intervals of lengths $d$ and $d+1$ for $m=2d+1$ , that every nonempty proper subset is strictly closer to some interval than to the trivial alternatives; it then claims the full formula $k_{\min}(C_m)=m-1$ . The argument has not been independently verified.

Current status (as of August 2026): The formula is established in the finite checked range and conditionally beyond it when the cyclic-interval lemma holds; the all-odd case remains open because the submitted proof is unverified.

Sources

arxiv.org

ProofThis solution needs a summarySee full solutionHide full solution

Proof of the cyclic-interval conjecture and the exact binary dimension of every odd cycle

Fokam Souop and Bitjoka, arXiv:2607.07939v1, Lemma 3 and Conjecture 1, ask whether, for every odd integer $m$ and every nonempty proper subset $X\subsetneq\mathbb Z_m$ , there exists a cyclic interval $W$ satisfying

|W\mathbin{\triangle}X| <\min\{|W|,m-|W|\}. \tag{1}

They prove this in one special geometric regime and verify the remaining cases only for $m\leq17$ . We prove (1) for every odd $m$ , and then derive the full conjectured binary embedding dimension.

An averaging identity for cyclic intervals

Write

m=2d+1, \qquad 1\leq w:=|X|\leq m-1. \tag{2}

For $1\leq L<m$ and $a\in\mathbb Z_m$ , define the cyclic interval

W_{a,L}=\{a,a+1,\ldots,a+L-1\}\subseteq\mathbb Z_m. \tag{3}

Each element of $X$ belongs to exactly $L$ of these $m$ intervals. Therefore

\sum_{a\in\mathbb Z_m}|W_{a,L}\cap X|=Lw. \tag{4}

The necessary interval length depends only on the parity of $w$ .

Case 1: $w$ is odd. Take $L=d$ . From (4), the average intersection size is

\frac{dw}{m} =\frac{w-1}{2}+\frac{m-w}{2m} >\frac{w-1}{2}, \tag{5}

where strictness follows from $w<m$ . Since intersection sizes are integers, some interval $W=W_{a,d}$ satisfies

|W\cap X|\geq\frac{w+1}{2}. \tag{6}

Consequently,

|W\mathbin{\triangle}X| =d+w-2|W\cap X| \leq d-1 <d =\min\{d,m-d\}. \tag{7}

Case 2: $w$ is even. Take $L=d+1$ . This time (4) gives

\frac{(d+1)w}{m} =\frac w2+\frac{w}{2m} >\frac w2, \tag{8}

since $w>0$ . Thus some interval $W=W_{a,d+1}$ satisfies

|W\cap X|\geq\frac w2+1. \tag{9}

It follows that

|W\mathbin{\triangle}X| =d+1+w-2|W\cap X| \leq d-1 <d =\min\{d+1,m-d-1\}. \tag{10}

Together, (7) and (10) prove (1) for every nonempty proper $X$ and every odd $m\geq3$ .

Consequence: the exact dimension of every odd cycle

Let $C_m$ have cyclically ordered vertices $v_0,\ldots,v_{m-1}$ , and suppose it embeds isometrically into a binary Cayley graph on $\mathbb F_2^k$ . For each edge define its generator

s_i=\phi(v_i)+\phi(v_{i+1})\in\mathbb F_2^k, \qquad i\in\mathbb Z_m. \tag{11}

Because the edges close to a cycle,

\sum_{i=0}^{m-1}s_i=0. \tag{12}

Introduce the dependency space

D=\left\{x\in\mathbb F_2^m: \sum_{i=0}^{m-1}x_i s_i=0\right\}. \tag{13}

Equation (12) states that the all-ones vector belongs to $D$ . If the generators $s_0,\ldots,s_{m-1}$ had rank at most $m-2$ , then $\dim D\geq2$ , so $D$ would contain the indicator of some nonempty proper subset $X\subsetneq\mathbb Z_m$ .

Choose the cyclic interval $W$ supplied by (1). If its endpoints on $C_m$ are $u$ and $v$ , then

\phi(u)+\phi(v) =\sum_{i\in W}s_i =\sum_{i\in W\mathbin{\triangle}X}s_i. \tag{14}

Every $s_i$ is an allowed generator of the host Cayley graph. Hence (14) exhibits a host walk from $\phi(u)$ to $\phi(v)$ of length at most $|W\triangle X|$ . But (1) gives

d_{\operatorname{Cay}}\!\left(\phi(u),\phi(v)\right) \leq |W\mathbin{\triangle}X| <\min\{|W|,m-|W|\} =d_{C_m}(u,v), \tag{15}

contradicting isometry. Therefore

k\geq\operatorname{rank}\{s_0,\ldots,s_{m-1}\}=m-1. \tag{16}

For completeness, this lower bound is attained. In $\mathbb F_2^{m-1}$ take

s_i=e_i\quad(0\leq i\leq m-2), \qquad s_{m-1}=e_0+\cdots+e_{m-2}. \tag{17}

Their only nonzero binary dependency uses all $m$ generators. Set

\phi(v_0)=0, \qquad \phi(v_j)=e_0+\cdots+e_{j-1} \quad(1\leq j\leq m-1). \tag{18}

For an arc $W$ , the only generator subsets representing its endpoint difference are $W$ and its complement. Because repeated generators cancel in characteristic $2$ , the host distance is exactly

\min\{|W|,m-|W|\}=d_{C_m}(u,v). \tag{19}

Thus this embedding is isometric, proving the full conjecture:

\boxed{\displaystyle k_{\min}(C_m)=m-1 \qquad\text{for every odd }m\geq3.} \tag{20}