# P2722: Maximum half-noise stability of a 794-set in the twelve cube

- ID: `P2722`
- Reference: `q12-noise-stability-794`
- Page: https://theoremdb.org/statements/P2722
- Record maturity: Reviewed problem with recorded work

## Problem

For \(A\subseteq\{0,1\}^{12}\) with \(|A|=794\), define \(E(A)=\sum_{x,y\in A}3^{12-d_H(x,y)}\). Determine the maximum of \(E(A)\) and classify the maximizers under cube automorphisms.

### Problem setup

- **Remark.** The objective is an integer multiple of the noise stability at correlation one half.
- **Definition.** Cube automorphisms consist of coordinate permutations and coordinate complements.

### What counts as a solution

- Give the exact maximum and all maximizing cube-automorphism orbits, with a certified upper bound matching an explicit set.

## Status

The binary initial segment supplies the lower endpoint. Walsh Parseval, Harper's edge bound, and an exact secant inequality supply the upper endpoint. [4](#reference-4)

## Work

### Evidence for the current status

**Computation 1 (The maximum lies between 6,456,734,424 and 7,623,232,012).** The binary initial segment supplies the lower endpoint. Walsh Parseval, Harper's edge bound, and an exact secant inequality supply the upper endpoint.

Let \(M_{12,794}\) denote the requested maximum. The certified result is
\[
6{,}456{,}734{,}424\leq M_{12,794}\leq7{,}623{,}232{,}012.
\]
The lower endpoint is attained by the explicit initial segment in q12ns794-claim-lex-witness.

For the upper bound, put \(f=1_A\), \(\mu=794/4096\), and use the normalized Walsh coefficients
\[
\widehat f(S)=2^{-12}\sum_x f(x)(-1)^{\sum_{i\in S}x_i}.
\]
The product kernel has Walsh eigenvalue \(4^{12-|S|}2^{|S|}\), hence
\[
E(A)=8^{12}\sum_{S\subseteq[12]}2^{-|S|}\widehat f(S)^2.
\]
Parseval gives \(R:=\sum_{S\ne\varnothing}\widehat f(S)^2=\mu-\mu^2=655447/4194304\). If \(b(A)\) is the undirected edge boundary, then
\[
D:=\sum_{S\ne\varnothing}|S|\widehat f(S)^2=\frac{b(A)}{2\cdot4096}.
\]
Harper's edge-isoperimetric theorem says that an initial binary segment maximizes the internal edges. At size 794 it has 3,693 internal edges, so every such \(A\) has \(b(A)\geq12\cdot794-2\cdot3693=2142\) and \(D\geq1071/4096\).

Convexity gives, for each integer \(1\leq k\leq12\),
\[
2^{-k}\leq\frac{12-k}{11}\,2^{-1}+\frac{k-1}{11}\,2^{-12}.
\]
Summing this inequality against the nonnegative Fourier weights and inserting the lower bound on \(D\) yields
\[
E(A)\leq\frac{83{,}855{,}552{,}164}{11}=7{,}623{,}232{,}014+\frac{10}{11}.
\]
For even \(|A|\), the objective is divisible by four: modulo four, the diagonal contributes \(|A|\) and the paired off-diagonal terms contribute \(2\binom{|A|}{2}\), whose sum is \(|A|^2\). The largest multiple of four below the rational bound is 7,623,232,012.

The endpoints do not match. The exact maximum and the cube-automorphism orbits of its maximizers remain open in this certificate.

### Background and intake notes

The lexicographic set improves the most symmetric Hamming-ball candidate by more than five hundred million objective units.

- Original intake status: Novelty remains unverified. No primary-source status audit was completed for this exact cardinality.
- The cardinality 794 equals the size of the Hamming ball through level four, yet the lexicographic initial segment gives a larger value.
- Edge-isoperimetric intuition sees only distance one, while every Hamming distance contributes to this kernel.
- Fourier or semidefinite bounds must encode the exact cardinality rather than relax it to a density interval.

- Recorded example: Compare the Hamming ball {x:|x|<=4} with the integer interval {0,...,793} in binary order.

### Other known results

- **Computation 2** (reproduced): With x encoded as the integer sum of 2^i x_i, take every integer from 0 through 793. [4](#reference-4)
- **Computation 3** (reproduced): The symmetric ball has the required size and trails the initial segment by 571,776,948. [4](#reference-4)

### Prior approaches

- **Route 1** (inconclusive): Harper settles the edge term, while average-distance and Boolean Fourier sources do not report this exact all-distance objective at size 794. [1](#reference-1) [3](#reference-3)

### Runnable artifacts

- **Artifact 1** (reproduced): A standard-library Python program checks both families by two exact methods and reproduces the rational universal upper bound. [4](#reference-4)

### Computational notes

- Exact integer kernel summation gave E=5884957476 for the Hamming ball and E=6456734424 for the lexicographic initial segment. Their conditional noise-retention probabilities are 0.4417768260393695 and 0.4846994480498191, respectively.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `q12-noise-stability-794`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1 entry has incomplete source metadata. Each affected row names the fields that still need editorial review.

1. <a id="reference-1"></a>André Kündgen, “Minimum average distance subsets in the hamming cube”. Discrete Mathematics 249(1-3) (2002), 149-165. DOI 10.1016/S0012-365X(01)00242-4. Harper, J. Combinatorial Theory 1 (1966), 385-393, DOI 10.1016/S0021-9800(66)80059-5; Bonami, Ann. Inst. Fourier 20 (1970), 335-402, https://www.numdam.org/item/AIF_1970__20_2_335_0/; Beckner, Ann. Math. 102 (1975), 159-182, DOI 10.2307/1970980; Kündgen, Discrete Math. 249 (2002), 149-165, DOI 10.1016/S0012-365X(01)00242-4 https://doi.org/10.1016/S0012-365X(01)00242-4
   - journal_article; primary source; version of record; checked 2026-08-01
   - Source use: original_summary
   - For Maximum half-noise stability of a 794-set in the twelve cube: Harper settles the edge term, while average-distance and Boolean Fourier sources do not report this exact all-distance objective at size 794.
2. <a id="reference-2"></a>William Beckner, “Inequalities in Fourier Analysis”. The Annals of Mathematics 102(1) (1975), 159. DOI 10.2307/1970980. The hypercontractive inequality on the discrete cube. https://doi.org/10.2307/1970980
   - journal_article; secondary source; checked 2026-08-01
   - Source use: original_summary
   - For Maximum half-noise stability of a 794-set in the twelve cube: Provides the sharp hypercontractive inequality behind the packet’s Fourier-analytic estimates.
3. <a id="reference-3"></a>Aline Bonami, “Étude des coefficients de Fourier des fonctions de L^p(G),” Annales de l’Institut Fourier 20(2) (1970), 335-402. DOI 10.5802/aif.357. Fourier-coefficient and hypercontractive inequalities developed in the article https://www.numdam.org/item/AIF_1970__20_2_335_0/
   - website; reference source; web version checked 2026-07-25; checked 2026-07-25
   - Source use: citation_only
   - For Maximum half-noise stability of a 794-set in the twelve cube, this source supplies the classical Fourier-analytic background used to bound the packet’s noise-stability objective.
4. <a id="reference-4"></a>Harper's edge-isoperimetric theorem combined with the exact verifier q12ns794-artifact-fourier-edge-verifier https://doi.org/10.1016/S0021-9800(66)80059-5
   - Also cited at Exact construction and two independent evaluations in q12ns794-artifact-fourier-edge-verifier
   - Also cited at Exact evaluations in q12ns794-artifact-fourier-edge-verifier
   - Also cited at Inline Python 3 verifier prepared on 2026-07-25
   - scholarly_publication; reference source
   - Source metadata incomplete: publication-style citation.
   - Source use: citation_only
   - Source named by the research packet.