Sets of uniqueness for the Ising model: u(k,2) = k+1, and the order of u(k,q)

Abstract

On the discrete cube X = {-1,+1}ᵏ let Bᵏ_q be the span of the Walsh functions of degree at most q and let (Bᵏ_q)₊ be its cone of non-negative members; Bᵏ₂ is the Ising model on the complete graph. A set U ⊆ X is a set of uniqueness for (Bᵏ_q)₊ if 0 is the only non-negative φ ∈ Bᵏ_q vanishing on U — the condition, due to Bogdan, Bosy and Skalski, under which the maximum likelihood estimator for the corresponding exponential family and a sample supported on U exists — and u(k,q) denotes the least size of such a set. Skalski and Stroiński proved u(k,2) ≤ k+1, proved lower bounds of order log k, and conjectured that u(k,2) = k+1. We prove the conjecture in the form u(k,2) = k+1 for every k ≥ 3, and observe that it is false as literally stated at k = 2, where u(2,2) = 4. The lower bound is a special case of a general one: every set of uniqueness for (Bᵏ₂ₘ)₊ has at least dim Bᵏₘ = Σ_(i ≤ m)C(k, i) points, so that u(k,q) ≥ Σ_(i ≤ ⌊ q/2 ⌋)C(k, i) for every q. Combined with the upper bound u(k,q) = O(k^(⌊ q/2⌋)) of Skalski and Stroiński this determines the order of u(k,q) for each fixed q, namely u(k,q) = Θ(k^(⌊ q/2 ⌋)), where the previously known lower bounds were logarithmic in k; and it is attained at q = k-1 for odd k. The mechanism of the lower bound is the classical one of Rao's bound for orthogonal arrays and of lower bounds for positive cubature formulae, transplanted to the weaker hypothesis; we say so plainly, and the statement, not the technique, is what is offered as new. We also correct a transcription of a formula of Kleitman and Spencer quoted in the source. All numbered results are machine-checked in Lean 4 against Mathlib and are general in k; Section [sec:verif] says exactly what is formalized, what is quoted, and which few numbers are computations rather than theorems.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-09-07 03:53 UTC

   File fingerprint

   8af5656716d628407db8ab963b98721ccb6eda2a2182ad1646144f78f1d3f8f5