gpt 6 astra ultra attempt on Math-620

The Snake-in-the-Box Problem

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

The hypercube $Q_n$ has vertex set $\{0,1\}^n$, with an edge between strings differing in exactly one coordinate. An induced path $v_0,\ldots,v_\ell$ has distinct vertices and an edge between two path vertices exactly when their indices differ by one. Its length is $\ell$ edges; its vertex count is $\ell+1$. Determine the maximum length. [S1] [S2]

Statement recorded in the supplied source.

What is the longest induced path in an n-dimensional hypercube graph? [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Determine exact values beyond dimension 8 and sharpen asymptotic bounds. [S1]

Short English statement

What is the longest path through a binary hypercube that has no shortcut edges between nonconsecutive path vertices?

Research attempt

Length convention and selected route.

Write $L(n)$ for the maximum number of edges in an induced path in $Q_n$. A path with $m$ vertices has $m-1$ edges throughout this attempt. The route combines a boundary-counting upper bound, a constructive dimension-lifting lower bound, and a small exhaustive search. Wynn's primary manuscript [E1] supplies context for more sophisticated snake and coil constructions; its historical records are not represented as the current optimal values in every dimension.

An upper bound from edges leaving the path.

Let $P$ be induced and have $m\ge2$ vertices. The cube is $n$-regular, and exactly $m-1$ edges have both endpoints in $P$. Summing degrees of vertices in $P$ therefore counts \[ nm-2(m-1)=(n-2)m+2 \] edges from $P$ to its complement. Each of the $2^n-m$ outside vertices receives at most $n$ such edges. Hence for $n\ge2$, \[ (n-2)m+2\le n(2^n-m),\qquad L(n)\le\left\lfloor\frac{n2^n-2}{2n-2}\right\rfloor-1. \] At $n=1$ the single cube edge gives $L(1)=1$ directly; one must not divide by $2n-2$ there. Inducedness is crucial: if the path vertex set had extra internal edges, subtracting only $2(m-1)$ from the degree sum would be wrong.

The bound treats every outside vertex as though it could meet the path in all $n$ neighbours independently. Those incidences are constrained by the cube and by the order of the path. Thus the inequality is generally loose. Equality in it would require every outside vertex to have all its neighbours inside the path, in addition to the path being induced. Merely attaining the numerical degree sum does not construct such a configuration.

Elementary paths and an exponential lifting construction.

Starting at the all-zero word and flipping coordinates $1,2,\ldots,n$ once each gives a path of length $n$. The Hamming distance between the vertices after $i$ and $j$ flips is $|i-j|$, so no nonconsecutive vertices are adjacent. Thus $L(n)\ge n$.

For a stronger recurrent construction, let $a_0,a_1,\ldots,a_{m-1}$ be any induced path in $Q_n$. In $Q_{n+2}$ take the sequence \[ (a_0,00),\ldots,(a_{m-1},00), (a_{m-1},01), (a_{m-1},11),\ldots,(a_0,11). \] Each consecutive pair is adjacent. The two long copies are individually induced; a vertex in layer $00$ is at distance at least two from a vertex in layer $11$. The sole vertex in layer $01$ is adjacent to a vertex of either copy only when its first $n$ coordinates equal $a_{m-1}$. Thus it introduces precisely its two intended neighbours and no chord. The new path has $2m+1$ vertices and $2m$ edges, giving \[ L(n+2)\ge2L(n)+2. \] For example the exact base $L(1)=1$ yields $L(2r+1)\ge3\cdot2^r-2$, and the base $L(2)=2$ yields $L(2r)\ge2^{r+1}-2$ for $r\ge1$. These are valid infinite families, not assertions of sharpness.

An exact exhaustive search with no unsafe symmetry reduction.

Encode cube vertices by integers $0,\ldots,2^n-1$, with adjacency when the exclusive-or has exactly one set bit. Translation by a cube vertex is an automorphism, so every induced path can be translated to start at zero. This justifies fixing its first vertex. The search then tries every unused neighbour $w$ of the current endpoint, accepting it only when it has no neighbour among the earlier path vertices other than that endpoint. The condition is exactly what is needed to preserve inducedness.

Inductively, every induced path beginning at zero occurs in this search tree: its next vertex is among the candidates and passes the condition. No unproved coordinate-permutation pruning is used. Recording the largest depth after visiting the whole finite tree therefore proves the optimum for the searched dimension, not only a lower bound. The implementation was executed for dimensions one through four and returned \[ L(1),L(2),L(3),L(4)=1,2,4,7. \] The numbers of visited search states were $2,5,22,305$, respectively. These are complete search-tree counts with the starting vertex fixed.

Concrete witnesses and reproducibility.

For dimensions three and four the saved integer-encoded witnesses are \[ 0,1,3,7,6 \quad\hbox{and}\quad 0,1,3,7,6,14,12,13. \] For example consecutive exclusive-ors in the latter are $1,2,4,1,8,2,1$, each a power of two; the program also verifies the nonconsecutive-neighbour exclusion at every extension. The first sequence has five vertices and four edges, the second eight vertices and seven edges. The audit files are checks_graphs.py and results_graphs.json in _Local/Erdos_problems/UnsolvedMath/attempt_audit_2026_10_01/number_theory/. No larger-dimensional exhaustive computation is claimed.

Remaining gap and outcome.

The construction grows roughly like $2^{n/2}$, while the elementary upper bound is of order $2^{n-1}$. Thus these arguments leave even an exponential gap in their asymptotic scales. Better concatenations must control cross-copy chords; better upper bounds must exploit cube structure beyond the total boundary capacity. The four exact finite values and the general inequalities do not determine $L(n)$ for all $n$. Outcome: UNRESOLVED. Neither the construction nor the small computed values are claimed as new records.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1423 (GRAPH-036), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 Snake-in-the-box overview. https://en.wikipedia.org/wiki/Snake-in-the-box. Bibliographic information from the supplied record.

• E1 Ed Wynn, Constructing circuit codes by permuting initial sequences, arXiv:1201.1647v1 $2012$. https://arxiv.org/abs/1201.1647. Primary abstract inspected 1 October 2026. It discusses constructions of snakes and coils; the historical record claims in that abstract are not updated here.