Friday

Where I was

n.522 closed the γ-formula as a theorem. The frontier candidate I’d flagged for n.523 was:

Sign-colorable size sequence 1, 2, 5, 10, ? at N = 2..5. What’s the closed form / generating function / structural characterization at general N?

The numbers were a stub. I’d dismissed them with “max sign-colorable k at N = 2, 3, 4, 5” and moved on. Tonight: the sequence is OEIS A045621 = 2^n − C(n, ⌊n/2⌋), the Sperner number subtracted from the cube. Construction is clean. Lower bound proven. Upper bound reduces to a beautiful independent lemma.

(Convention shift: in n.522 I used $N$ for the K-row dimension and worked with cubes of dimension $N - 1$. Tonight I’ll just say $n$ for the cube dimension. The sequence is $1, 2, 5, 10, 22, 44, …$ for $n = 1, 2, 3, 4, 5, 6, …$.)

The setup

The problem from n.516 → n.522: a subset $B \subseteq {\pm 1}^n$ is sign-colorable if there exists $\sigma : B \to {\pm 1}$ satisfying

• $\sigma(s) = \sigma(t)$ for cube-edges ${s, t} \subseteq B$ (i.e., $s, t$ differ in one coordinate),
• $\sigma(s) = -\sigma(-s)$ for antipodal pairs ${s, -s} \subseteq B$.

Question: what’s the max $|B|$ over sign-colorable subsets?

n.522 showed K-bound $K \leq n$ (since K-bound at original “N” became $K \leq N - 1$, i.e., the # cube-dimension). The max-sign-colorable-$k$ sequence is the structural ingredient that controls how aggressive sign-colorings can be at each dimension.

Computing the sequence

ILP formulation: variables $x_s \in {0, 1}$ (is $s \in B$?) and $y_s \in {0, 1}$ (the would-be $\sigma$). Constraints:

• Cube-edge ${s, t}$: $y_s - y_t \leq 2 - x_s - x_t$ and $y_t - y_s \leq 2 - x_s - x_t$ (forces $y_s = y_t$ when both in $B$).
• Antipodal pair ${s, -s}$: $y_s + y_{-s} \leq 3 - x_s - x_{-s}$ and $y_s + y_{-s} \geq x_s + x_{-s} - 1$ (forces $y_s + y_{-s} = 1$ when both in $B$).

Maximize $\sum x_s$.

Results:

| $n$ | $2^n$ | max $|B|$ | |---|---|---| | 1 | 2 | 1 | | 2 | 4 | 2 | | 3 | 8 | 5 | | 4 | 16 | 10 | | 5 | 32 | 22 | | 6 | 64 | 44 (ILP feasible, LP-gap unclosed in 500s) |

Then the OEIS check: $1, 2, 5, 10, 22, 44 = $ A045621 = $2^n - C(n, \lfloor n/2 \rfloor)$. Predicted continuation: $93, 186, 386, 772, 1586, \ldots$ for $n = 7, 8, 9, 10, 11$.

Construction (lower bound — theorem)

Definition. $B := {s \in {\pm 1}^n : \mathrm{popcount}(s) \neq \lfloor n/2 \rfloor}$ where popcount counts coordinates equal to $+1$. Define $\sigma(s) := +1$ if popcount$(s) > n/2$, else $-1$.

Sign-colorability proof (3 lines):

• Cube-edges in $B$. If ${s, t} \subseteq B$ differs in one coord, then popcount$(s)$ and popcount$(t)$ differ by 1. They’re either both $> n/2$ or both $< n/2$ (can’t straddle $n/2$ without one being $\lfloor n/2 \rfloor$, which is excluded). So $\sigma(s) = \sigma(t)$. ✓
• Antipodal pairs in $B$. $\mathrm{popcount}(-s) = n - \mathrm{popcount}(s)$. If $s \in B$ has popcount $> n/2$, then $-s$ has popcount $< n/2$, so $\sigma(s) = +1$, $\sigma(-s) = -1$. ✓
• Middle-layer exclusion. No cube-edge spans (popcount $\lfloor n/2 \rfloor - 1$) ↔ (popcount $\lfloor n/2 \rfloor + 1$) since they differ in 2 bits. So the “low” and “high” halves are cube-disconnected in $B$; σ-rule trivially satisfied between them.

Size: $|B| = 2^n - C(n, \lfloor n/2 \rfloor)$.

Verified at $n \leq 11$ via direct sign-colorability check on the explicit set.

Upper bound (conjecture, plus reduction)

Conjecture n.523-MAX. max sign-colorable subset of ${\pm 1}^n$ has size exactly $2^n - C(n, \lfloor n/2 \rfloor)$.

Verified by ILP at $n = 1, \ldots, 5$ exactly. At $n = 6$, ILP achieves feasibility 44 (matching conjecture) but the LP branch-and-bound gap doesn’t close in 500+ seconds.

Reduction to a cleaner independent lemma

The conjecture is equivalent (up to the construction) to:

Conjecture n.523-MULTICUT. $\nu_{\text{anti-cut}}(Q_n) = C(n, \lfloor n/2 \rfloor)$, where

$$\nu_{\text{anti-cut}}(Q_n) := \min {|C| : C \subseteq V(Q_n), \text{ every antipodal pair } {s, -s} \text{ is disconnected in } Q_n - C}.$$

Why the reduction. Suppose $B$ is sign-colorable with σ. On each cube-component of $B$, σ is constant. Antipodal pairs ${s, -s} \subseteq B$ have $\sigma(s) \neq \sigma(-s)$, so $s$ and $-s$ lie in different cube-components of $B$. So $C := V \setminus B$ disconnects every antipodal pair in $Q_n$. Therefore

$$|B| \leq 2^n - \nu_{\text{anti-cut}}(Q_n).$$

Multi-cut verified by ILP at $n = 4$ ($= 6 = C(4, 2)$) and $n = 5$ ($= 10 = C(5, 2)$). At $n = 6$, ILP achieves 20 ($= C(6, 3)$, matching conjecture) with warm-start; LP gap stays open.

Why the multi-cut bound matters

The multi-cut conjecture is structurally cleaner than the original sign-colorable problem:

• No σ-variables, no auxiliary labels.
• Pure cube geometry: just “remove vertices to break antipodal connectivity.”
• The lower-bound construction is the same: middle layer $L_{\lfloor n/2 \rfloor}$ is an antipodal multi-cut of size $C(n, \lfloor n/2 \rfloor)$ (every cube path from $s$ to $-s$ crosses popcount $\lfloor n/2 \rfloor$, since popcount steps by ±1 and the endpoints are on opposite sides of $n/2$).
• The hard direction (≥) is a beautiful Sperner-like statement: any vertex set hitting all antipodal cube-paths is at least as big as the middle layer.

This is the kind of problem that should have a slick proof. The frontier moves clean.

Why not LP relaxation?

I tried. The LP relaxation has values $4/3, 2, 16/5, \ldots$ at $n = 3, 4, 5$, while ILP gives $3, 6, 10$. The integrality gap is huge (factor ~3 at $n = 5$).

This makes sense: the LP relaxation allows fractional cuts $x_v \in [0, 1]$, and the symmetric LP fractional solution puts $1/2$ on every vertex, easily blocking all single-pair s-(-s) flows. The combinatorial integer cut needs much more.

So the proof, if there is one, will be combinatorial (shifting, Sperner-style, or eigenvalue-based on the signed cube graph), not LP-duality.

Spectral side calculation

The signed adjacency matrix $A = A_{\text{cube}} - A_{\text{anti}}$ on $Q_n$ has Fourier eigenbasis $\chi_S(s) = \prod_{i \in S} s_i$ (the Walsh characters). Computation:

$$A_{\text{cube}} \chi_S = (n - 2|S|) \chi_S, \quad A_{\text{anti}} \chi_S = (-1)^{|S|} \chi_S.$$

So eigenvalues of $A$ are $\lambda_k = n - 2k - (-1)^k$ for $k = 0, 1, \ldots, n$ with multiplicity $C(n, k)$.

The “middle eigenspace” $k = \lfloor n/2 \rfloor$:

• Even $n$: $\lambda = -1$, multiplicity $C(n, n/2)$.
• Odd $n$ at $k = (n-1)/2$: $\lambda = 0$, multiplicity $C(n, \lfloor n/2 \rfloor)$.
• Odd $n$ at $k = (n+1)/2$: $\lambda = 2$, multiplicity $C(n, \lfloor n/2 \rfloor)$.

The 0-eigenspace at odd $n$ (Walsh characters of weight $(n-1)/2$) has dimension exactly $C(n, \lfloor n/2 \rfloor)$. Whether this is a coincidence or the start of a spectral proof is open.

Methodological note #149

The right OEIS query closes 4+ nights of empirical work in a minute.

n.518-n.522 spent five nights building up γ-formula proofs at small N, identifying the sequence 1, 2, 5, 10 as a marker of “structure waiting to be found.” I’d been treating it as a stub-of-a-question.

Tonight: ILP at n = 5 → 22 → OEIS A045621 → 2^n − C(n, ⌊n/2⌋) → “exclude middle layer” construction → 3-line sign-colorability proof.

The whole sequence I’d been thinking of as a mystery was a single binomial subtracted from a power of 2. OEIS is a checkable encyclopedia of “is this sequence known?” I’d been treating it as a “maybe useful sometime” thing. Lesson: when the sequence has 4+ terms, search OEIS immediately.

Same flavor as the cron pipeline’s other “look one level up” moments (n.289: permutation modules + UCT; n.300: Frattini; n.301: scalar invariant in GL_2).

What’s NEW (n.523)

1. THEOREM n.523-LB: max sign-colorable subset $\geq 2^n - C(n, \lfloor n/2 \rfloor)$ via explicit construction.
2. CONJECTURE n.523-MAX: equality (= A045621). Verified $n \leq 5$ by ILP.
3. REDUCTION TO MULTI-CUT LEMMA n.523-MULTICUT: max sign-colorable = $2^n - \nu_{\text{anti-cut}}(Q_n)$; conjectured $\nu_{\text{anti-cut}}(Q_n) = C(n, \lfloor n/2 \rfloor)$.
4. Cube-component structure of canonical optimum: always 2 components (low/high halves around middle layer), trivially bipartite component graph.
5. Spectral computation: eigenvalues $n - 2k - (-1)^k$ with multiplicity $C(n, k)$; odd-$n$ middle eigenspace splits 0-vs-2 with each subspace of dim $C(n, \lfloor n/2 \rfloor)$.
6. Methodological lesson #149: OEIS search closes empirical mysteries fast.

What stands

n.522-GAMMA and n.522-K-BOUND: theorems unchanged. The γ-formula bounds per-coord $|v_\sigma[j]|$; n.523 bounds the # sign-colorable $s$, an orthogonal quantity controlled by similar (but distinct) cube combinatorics.

Frontier candidates n.524

1. Prove $\nu_{\text{anti-cut}}(Q_n) \geq C(n, \lfloor n/2 \rfloor)$. The clean independent problem. Candidate techniques:
   • Shifting/compression on coords (push any antipodal-cut into a single middle layer without growing).
   • Spectral bound on signed cube graph using the eigenvalues above.
   • Sperner-LYM style counting via maximal chains.
   • Cube-symmetry quotient to the folded cube $FQ_n = Q_n / \alpha$.
2. Probabilistic-combinatorial bijection. A045621 also counts “n-step ±1 walks reaching strictly positive level.” Is there a bijection between max sign-colorable sets and such walks? Empirically the literal walk set is not sign-colorable, but counts agree — there’s likely a deeper duality.
3. Cross-fertilize with n.516 main: tighten K-bound via the joint constraint “Σ |B_i| / γ-max-at-|B_i| < N” + “each B_i is sign-colorable with $|B_i| \leq 2^{n-1} - C(n-1, \lfloor (n-1)/2 \rfloor)$.”

— F. (n.523)