# Random Saturation and Optimal Off-Origin Slack in Real Homogeneous Boolean Threshold Boxes
## Abstract
We study bounded-height homogeneous real polynomial lifts of Boolean sign functions. A homogeneous form of degree (D) in variables \(X_0,\dots,X_n\), with all homogeneous coefficients bounded in absolute value by (1), induces on the affine Boolean chart
$$
(X_0,X_1,\dots,X_n)=(1,x_1,\dots,x_n),
\qquad x_i\in{0,1},
$$
a multilinear polynomial
$$
p(x)=\sum_{S\subseteq[n]}a_Sx_S
$$
whose coefficients satisfy the exact box constraints
$$
|a_S|\le \binom{D}{|S|}.
$$
Conversely, every coefficient vector satisfying these inequalities arises from a homogeneous degree-(D) form of coefficient height at most (1).
For a Boolean sign function \(G:{0,1}^n\to{\pm1}\), define the real box margin
$$
\gamma_D(G)=
\max_{|a_S|\le \binom{D}{|S|}}
\min_{T\subseteq[n]}
G_T\sum_{S\subseteq T}a_S.
$$
Since the empty point sees only \(a_\varnothing\), one always has
$$
\gamma_D(G)\le1.
$$
Let \(H_2\) denote the binary entropy function, and let (\rho_\in(1/2,1)) be the unique solution of
$$
H_2(\rho_*)=\rho_*.
$$
Numerically,
$$
\rho_*=0.7729078047\ldots,
\qquad
\frac1{2\rho_*}=0.6469076867\ldots.
$$
We prove that if \(D_n\) is a linear degree sequence satisfying
$$
0<\liminf_{n\to\infty}\frac{D_n}{n}
\le
\limsup_{n\to\infty}\frac{D_n}{n}
<\infty
$$
and
$$
\liminf_{n\to\infty}\frac{D_n}{n}>
\frac1{2\rho_*},
$$
then for uniformly random \(G_n:{0,1}^n\to{\pm1}\),
$$
\Pr(\gamma_{D_n}(G_n)=1)\to1.
$$
The main theorem is sharper. After fixing the empty coefficient to saturate the origin, the optimal margin on every non-origin Boolean point is asymptotically maximal:
$$
\eta_{D_n}(G_n)=D_n-1-o(1)
\qquad\text{with high probability}.
$$
Thus, in this bounded-height homogeneous real model, the origin is the unique bottleneck.
The proof combines exact minimax duality for boxes, a sharp weighted upward-zeta localization estimate, a complement transform converting high-zeta data into low-degree Boolean polynomials, and a projection-separation lemma showing that a random signed simplex is far in \(\ell^1\) from every sufficiently low-dimensional polynomial subspace.
All results in this paper are over real coefficients. They do not imply integer, ternary, or rounded coefficient representations.

## 1. Introduction
A classical question in Boolean function analysis asks for the degree needed to sign-represent a Boolean function by a real polynomial. In the unbounded-coefficient setting, random Boolean functions have threshold degree near (n/2). This paper studies a different model: real polynomial representations arising from homogeneous forms of bounded coefficient height.
Let
$$
F\in \mathbb{R}[X_0,\dots,X_n]_D
$$
be homogeneous of degree (D). Restrict (F) to the affine Boolean chart
$$
(X_0,X_1,\dots,X_n)=(1,x_1,\dots,x_n),
\qquad x_i\in{0,1},
$$
and reduce by the Boolean relations
$$
x_i^2=x_i.
$$
If every homogeneous coefficient of (F) has absolute value at most (1), the resulting multilinear polynomial
$$
p(x)=\sum_{S\subseteq[n]}a_Sx_S
$$
satisfies
$$
|a_S|\le \binom{D}{|S|}.
$$
Conversely, every multilinear coefficient vector satisfying these inequalities is realized by some homogeneous degree-(D) form with coefficient height at most (1). Thus the coefficient body induced by height-one homogeneous degree-(D) forms is exactly
$$
\mathcal B_{n,D}
\left\{
a=(a_S)_{S\subseteq[n]}:
|a_S|\le \binom{D}{|S|}
\right\},
$$
with the convention
$$
\binom{D}{s}=0
\qquad (s>D).
$$
For \(G:{0,1}^n\to{\pm1}\), define
$$
\gamma_D(G)=
\max_{a\in\mathcal B_{n,D}}
\min_{T\subseteq[n]}
G_T\sum_{S\subseteq T}a_S.
$$
At the empty point \(T=\varnothing\), the polynomial value is simply \(a_\varnothing\). Since
$$
|a_\varnothing|\le 1,
$$
one always has
$$
\gamma_D(G)\le1.
$$
We prove that this upper bound is attained with high probability for random (G) once
$$
D>(0.646907\ldots)n.
$$
More precisely, in the linear degree regime
$$
D_n=\Theta(n),
$$
if
$$
\liminf_{n\to\infty}\frac{D_n}{n}>
\frac1{2\rho_*},
$$
then
$$
\gamma_{D_n}(G_n)=1
$$
with high probability.
The theorem is stronger than saturation. After fixing \(a_\varnothing\) to saturate the origin, the optimal margin on every nonempty Boolean point is
$$
D_n-1-o(1),
$$
which is asymptotically the largest possible margin forced by singleton constraints.
This is a bounded-coefficient random representation theorem for a concrete homogeneous coefficient body. It is not an unbounded-coefficient threshold-degree theorem.

## 2. Homogeneous coefficient boxes
We identify a Boolean vector \(x\in{0,1}^n\) with its support
$$
T={i:x_i=1}\subseteq[n].
$$
For \(S\subseteq[n]\), write
$$
x_S=\prod_{i\in S}x_i.
$$
Let
$$
F\in\mathbb{R}[X_0,\dots,X_n]_D
$$
be homogeneous of degree (D). A monomial
$$
X_0^{\alpha_0}X_1^{\alpha_1}\cdots X_n^{\alpha_n},
\qquad
\sum_{i=0}^n\alpha_i=D,
$$
reduces on the affine Boolean chart to \(x_S\) precisely when
$$
\alpha_i\ge1 \quad (i\in S),
$$
and
$$
\alpha_j=0 \quad (j\notin S,\ j\ge1).
$$
Thus the number of homogeneous degree-(D) monomials reducing to \(x_S\) is the number of solutions
$$
\alpha_0+\sum_{i\in S}\alpha_i=D,
\qquad
\alpha_0\ge0,
\qquad
\alpha_i\ge1\quad(i\in S).
$$
Equivalently, after writing
$$
\beta_i=\alpha_i-1\quad(i\in S),
$$
we count nonnegative solutions of
$$
\alpha_0+\sum_{i\in S}\beta_i=D-|S|.
$$
The number is
$$
\binom{D}{|S|}.
$$
Therefore, if every homogeneous coefficient of (F) lies in ([-1,1]), the induced Boolean coefficient \(a_S\) satisfies
$$
|a_S|\le \binom{D}{|S|}.
$$
Conversely, suppose
$$
|a_S|\le \binom{D}{|S|}
$$
for every \(S\subseteq[n]\). For each (S), distribute the real number \(a_S\) evenly among the \(\binom{D}{|S|}\) homogeneous monomials reducing to \(x_S\). Each assigned homogeneous coefficient has absolute value at most (1), and the resulting homogeneous degree-(D) form restricts to the given multilinear polynomial on the Boolean cube.
Hence the exact real coefficient box induced by homogeneous degree-(D), height-one forms is
$$
\mathcal B_{n,D}
\left\{
a=(a_S)_{S\subseteq[n]}:
|a_S|\le \binom{D}{|S|}
\right\}.
$$

## 3. Margins and off-origin slack
Let
$$
G:{0,1}^n\to{\pm1},
$$
and write
$$
G_T=G(1_T).
$$
Define the full box margin
$$
\gamma_D(G)=
\max_{|a_S|\le \binom{D}{|S|}}
\min_{T\subseteq[n]}
G_T\sum_{S\subseteq T}a_S.
$$
As noted above,
$$
\gamma_D(G)\le1.
$$
Because the coefficient box is centrally symmetric,
$$
\gamma_D(G)=\gamma_D(-G).
$$
Thus we may normalize
$$
G_\varnothing=1
$$
when proving lower bounds.
For unnormalized (G), define the off-origin margin by fixing the empty coefficient to saturate the origin:
$$
\eta_D(G)
\max_{\substack{|a_S|\le \binom{D}{|S|}\ a_\varnothing=G_\varnothing}}
\min_{\varnothing\ne T\subseteq[n]}
G_T\sum_{S\subseteq T}a_S.
$$
After multiplying (G) by \(G_\varnothing\), this is equivalent to the normalized setting
$$
G_\varnothing=1,
\qquad
a_\varnothing=1.
$$
If
$$
\eta_D(G)\ge1,
$$
then
$$
\gamma_D(G)=1.
$$
Indeed, the empty point has margin exactly (1), and every nonempty point has margin at least (1).
The main theorem proves much more:
$$
\eta_{D_n}(G_n)=D_n-1-o(1)
$$
with high probability for random \(G_n\), in the linear degree regime above the threshold
$$
\frac1{2\rho_*}.
$$

## 4. Exact minimax duality
We first record a general box-duality statement.
Let
$$
B=(B_S){S\subseteq[n]}
$$
be a nonnegative weight system, and define
$$
\gamma_B(G)=
\max_{|a_S|\le B_S}
\min_{T\subseteq[n]}
G_T\sum_{S\subseteq T}a_S.
$$
Let
$$
\Delta(2^{[n]})
$$
denote the probability simplex on all subsets of ([n]).
Theorem 4.1. Box duality
For every \(G:{0,1}^n\to{\pm1}\),
$$
\gamma_B(G)
\min_{\lambda\in\Delta(2^{[n]})}
\sum_{S\subseteq[n]}B_S
\left|
\sum_{T\supseteq S}\lambda_TG_T
\right|.
$$
Proof
For fixed (a=\(a_S\)), put
$$
L_T(a)=G_T\sum_{S\subseteq T}a_S.
$$
Then
$$
\min_TL_T(a)
\min_{\lambda\in\Delta(2^{[n]})}
\sum_T\lambda_TL_T(a).
$$
Hence
$$
\gamma_B(G)
\max_{|a_S|\le B_S}
\min_{\lambda\in\Delta(2^{[n]})}
\sum_T\lambda_TG_T\sum_{S\subseteq T}a_S.
$$
The coefficient box and the simplex are compact convex sets, and the objective is bilinear. By finite-dimensional minimax duality,
$$
\gamma_B(G)
\min_{\lambda\in\Delta(2^{[n]})}
\max_{|a_S|\le B_S}
\sum_Sa_S
\sum_{T\supseteq S}\lambda_TG_T.
$$
For fixed \(\lambda\), the inner maximum is the support function of the box:
$$
\max_{|a_S|\le B_S}\sum_Sa_Sc_S
\sum_SB_S|c_S|.
$$
Taking
$$
c_S=\sum_{T\supseteq S}\lambda_TG_T
$$
gives the result. \(\square\)

## 5. Duality for off-origin slack
Assume throughout this section that
$$
G_\varnothing=1.
$$
For a probability measure \(\nu\) on nonempty subsets, define
$$
A_G(\nu)=
\sum_{T\ne\varnothing}\nu_TG_T
$$
and
$$
B_{D,G}(\nu)
\sum_{\substack{S\ne\varnothing\ |S|\le D}}
\binom{D}{|S|}
\left|
\sum_{\substack{T\supseteq S\\ T\ne\varnothing}}\nu_TG_T
\right|.
$$
Proposition 5.1. Dual form of off-origin slack
For \(G_\varnothing=1\),
$$
\eta_D(G)
\min_{\nu\in\Delta(2^{[n]}\setminus{\varnothing})}
\left[
A_G(\nu)+B_{D,G}(\nu)
\right].
$$
Proof
In the definition of \(\eta_D\), the coefficient \(a_\varnothing\) is fixed to (1), and the variables are \(a_S\) for \(S\ne\varnothing\). For a probability measure \(\nu\) on nonempty (T), the averaged objective is
$$
\sum_{T\ne\varnothing}\nu_TG_T
\left(
1+
\sum_{\substack{S\subseteq T\S\ne\varnothing}}a_S
\right).
$$
This equals
$$
A_G(\nu)
+
\sum_{S\ne\varnothing}a_S
\sum_{\substack{T\supseteq S\\ T\ne\varnothing}}\nu_TG_T.
$$
Applying minimax over the coefficient box for the variables \(a_S\), \(S\ne\varnothing\), the maximum over
$$
|a_S|\le \binom{D}{|S|}
$$
is precisely
$$
B_{D,G}(\nu).
$$
Thus
$$
\eta_D(G)
\min_\nu
\left[
A_G(\nu)+B_{D,G}(\nu)
\right].
$$
\(\square\)
Since always
$$
A_G(\nu)\ge-1,
$$
a uniform lower bound on (B_{D,G}\(\nu\)) gives an off-origin slack lower bound.

## 6. Sharp weighted upward-zeta localization
Let \(\nu\) be a probability measure on nonempty subsets and define
$$
\theta_T=\nu_TG_T,
\qquad T\ne\varnothing.
$$
Then
$$
|\theta|_1=1.
$$
Define the upward-zeta transform of \(\theta\) by
$$
h_S=
\sum_{\substack{T\supseteq S\\ T\ne\varnothing}}\theta_T,
\qquad S\ne\varnothing.
$$
Then
$$
B_{D,G}(\nu)
\sum_{\substack{S\ne\varnothing\ |S|\le D}}
\binom{D}{|S|}|h_S|.
$$
For \(1\le r\le D\), let \(h^{\le r}\) be the restriction of (h) to levels
$$
1\le |S|\le r.
$$
Let \(\theta^{\le r}\) be the Möbius inverse of this truncated zeta transform:
$$
\theta_T^{\le r}
\sum_{\substack{S\supseteq T\\ 1\le |S|\le r}}
(-1)^{|S|-|T|}h_S,
\qquad T\ne\varnothing.
$$
Define
$$
\mathfrak m^*(D,r)
\max_{1\le s\le r}
\frac{2^s-1}{\binom{D}{s}}.
$$
Lemma 6.1. Sharp truncated inverse bound
For every \(\nu\),
$$
|\theta^{\le r}|_1
\le
\mathfrak m^*(D,r)B_{D,G}(\nu).
$$
Proof
By the triangle inequality,
$$
|\theta_T^{\le r}|
\le
\sum_{\substack{S\supseteq T\\ 1\le |S|\le r}}|h_S|.
$$
Summing over all nonempty (T),
$$
|\theta^{\le r}|_1
\le
\sum_{1\le |S|\le r}
|{T\ne\varnothing:T\subseteq S}|,|h_S|.
$$
For fixed \(S\ne\varnothing\),
$$
|{T\ne\varnothing:T\subseteq S}|=2^{|S|}-1.
$$
Therefore
$$
|\theta^{\le r}|_1
\le
\sum_{1\le |S|\le r}(2^{|S|}-1)|h_S|.
$$
Hence
$$
|\theta^{\le r}|_1
\le
\left(
\max_{1\le s\le r}
\frac{2^s-1}{\binom{D}{s}}
\right)
\sum_{1\le |S|\le r}
\binom{D}{|S|}|h_S|
\le
\mathfrak m^*(D,r)B_{D,G}(\nu).
$$
\(\square\)
The upward-zeta transform of \(\theta^{\le r}\) agrees with (h) on all nonempty levels \(1\le |S|\le r\) and vanishes on nonempty levels \(|S|>r\). Hence, if
$$
\theta^{>r}=\theta-\theta^{\le r},
$$
then the upward-zeta transform of \(\theta^{>r}\) vanishes on all nonempty levels
$$
1\le |S|\le r.
$$

## 7. Complement transform and low-degree polynomials
Let
$$
\theta^{>r}=\theta-\theta^{\le r}.
$$
The upward-zeta transform of \(\theta^{>r}\) vanishes on every nonempty level
$$
1\le |S|\le r.
$$
Let
$$
\Omega_n^\circ={U\subseteq[n]:U\ne[n]}.
$$
For \(U\in\Omega_n^\circ\), set
$$
T=U^c.
$$
Then \(T\ne\varnothing\). Define
$$
q(U)=(-1)^{|U|}\theta^{>r}_{U^c}.
$$
Lemma 7.1. Complement-degree lemma
The function (q) is the restriction to \(\Omega_n^\circ\) of a real multilinear polynomial of degree at most (n-r).
Proof
Let \(h^{>r}\) be the upward-zeta transform of \(\theta^{>r}\). Möbius inversion gives
$$
\theta_T^{>r}
\sum_{S\supseteq T}
(-1)^{|S|-|T|}h_S^{>r}.
$$
Put
$$
T=U^c
\qquad\text{and}\qquad
R=S^c.
$$
Then \(S\supseteq T\) is equivalent to \(R\subseteq U\), and
$$
|S|-|T|
(n-|R|)-(n-|U|)
|U|-|R|.
$$
Therefore
$$
q(U)
(-1)^{|U|}\theta^{>r}_{U^c}
\sum_{R\subseteq U}
(-1)^{|R|}h^{>r}_{R^c}.
$$
Since \(h_S^{>r}=0\) whenever \(S\ne\varnothing\) and \(|S|\le r\), all nonzero terms satisfy
$$
|R^c|>r.
$$
Equivalently,
$$
|R|<n-r.
$$
Thus (q) is represented by a multilinear polynomial of degree at most (n-r-1), and hence certainly of degree at most (n-r). \(\square\)

## 8. Projection separation from signed simplices
Let \(\Omega\) be a finite set and let
$$
V\subseteq\mathbb{R}^\Omega
$$
be a linear subspace. Let
$$
\xi\in{\pm1}^{\Omega}.
$$
Define the signed simplex
$$
\mathcal C_\xi=
{\xi\cdot\mu:\mu\in\Delta(\Omega)},
$$
where
$$
(\xi\cdot\mu)\omega=\xi\omega\mu_\omega.
$$
Let \(\Pi_V\) be the orthogonal projection onto (V) with respect to the counting inner product
$$
\langle f,g\rangle
\sum_{\omega\in\Omega}f_\omega g_\omega.
$$
Lemma 8.1. Projection separation
If
$$
|\Pi_V\xi|_\infty\le\tau,
$$
then for every \(q\in V\) and every (\mu\in\Delta\(\Omega\)),
$$
|q-\xi\cdot\mu|_1
\ge
\frac{1-\tau}{1+\tau}.
$$
Proof
Let
$$
\delta=|q-\xi\cdot\mu|_1.
$$
Since
$$
\langle \xi,\xi\cdot\mu\rangle
\sum_{\omega}\mu_\omega
1,
$$
we have
$$
\langle \xi,q\rangle
1+\langle \xi,q-\xi\cdot\mu\rangle
\ge
1-\delta.
$$
Also,
$$
|q|_1
\le
|\xi\cdot\mu|_1+\delta
1+\delta.
$$
Since \(q\in V\),
$$
\langle \xi,q\rangle
\langle \Pi_V\xi,q\rangle
\le
|\Pi_V\xi|_\infty|q|_1
\le
\tau(1+\delta).
$$
Combining the last two inequalities,
$$
1-\delta\le \tau(1+\delta),
$$
and hence
$$
\delta\ge \frac{1-\tau}{1+\tau}.
$$
\(\square\)

## 9. Random projection on the punctured cube
Let
$$
\Omega_n={0,1}^n,
\qquad
N=2^n.
$$
We identify \(\Omega_n\) with \(2^{[n]}\). Let
$$
x_*=[n]
$$
be the top point, and set
$$
\Omega_n^\circ=\Omega_n\setminus{x_*}.
$$
Let \(L_{\le d}\) be the space of real multilinear polynomials of degree at most (d) on the full cube, and let \(W_{\le d}\) be its restriction to \(\Omega_n^\circ\). Put
$$
M=\binom{n}{\le d}.
$$
Lemma 9.1. Punctured projection estimate
Assume
$$
d<n
\qquad\text{and}\qquad
M/N\to0.
$$
Let
$$
\xi\in{\pm1}^{\Omega_n^\circ}
$$
be uniformly random. Let \(\Pi\) be the orthogonal projection onto \(W_{\le d}\) in (\ell^2\(\Omega_n^\circ\)). Then
$$
|\Pi\xi|_\infty
O_{\mathbb{P}}
\left(
\sqrt{\frac{Mn}{N}}
\right).
$$
In particular, if
$$
M/N\le2^{-\alpha n}
$$
for some \(\alpha>0\), then
$$
|\Pi\xi|_\infty=2^{-\Omega(n)}
$$
with high probability.
Proof
First, the restriction map
$$
L_{\le d}\to W_{\le d}
$$
is injective. Indeed, if \(P\in L_{\le d}\) vanished on all points of the cube except possibly \(x_*=[n]\), then, as a function on the full cube, it would be a scalar multiple of
$$
\mathbf 1_{{[n]}}(x)=x_1x_2\cdots x_n.
$$
This function has multilinear degree (n). Since \(d<n\), such a polynomial (P) must be zero. Hence
$$
\dim W_{\le d}=M.
$$
On the full cube, normalized Walsh characters of degree at most (d) form an orthonormal basis of \(L_{\le d}\). Hence the full projection matrix (P) onto \(L_{\le d}\) has diagonal
$$
P_{xx}=M/N
$$
for every \(x\in\Omega_n\).
Let (E) be the \(N\times M\) matrix with orthonormal columns spanning \(L_{\le d}\). Let (v) be the row of (E) corresponding to the deleted point \(x_*\). After deleting this row, the Gram matrix becomes
$$
I-vv^{\mathsf{T}}.
$$
Since
$$
|v|_2^2=P_{x_*x_*}=M/N<1
$$
for all large (n), its inverse is
$$
(I-vv^{\mathsf{T}})^{-1}
I+\frac{vv^{\mathsf{T}}}{1-|v|_2^2}.
$$
Therefore, for \(x\ne x_*\), the restricted projection matrix (P') satisfies
$$
P'_{xx}
=
P_{xx}
+
\frac{P_{xx_*}^2}{1-P_{x_*x_*}}.
$$
Since (P) is positive semidefinite,
$$
P_{xx_*}^2
\le
P_{xx}P_{x_*x_*}
\left(\frac MN\right)^2.
$$
Therefore, for all large (n),
$$
P'_{xx}\le \frac{2M}{N}.
$$
For fixed \(x\in\Omega_n^\circ\),
$$
(\Pi\xi)(x)=\sum_{y\in\Omega_n^\circ}P'_{xy}\xi_y.
$$
Since (P') is an orthogonal projection,
$$
\sum_y(P'_{xy})^2=P'_{xx}\le\frac{2M}{N}.
$$
Hoeffding's inequality gives
$$
\Pr\left(|(\Pi\xi)(x)|>t\right)
\le
2\exp\left(-\frac{t^2}{4M/N}\right).
$$
Taking
$$
t=A\sqrt{\frac{Mn}{N}}
$$
with (A) sufficiently large and union-bounding over at most (N) points proves the first claim. If \(M/N\le2^{-\alpha n}\), then this bound is exponentially small in (n). \(\square\)

## 10. A general off-origin slack criterion
Let \(D_n,r_n\) be integer sequences satisfying
$$
1\le r_n\le \min(D_n,n)
$$
eventually. Put
$$
d_n=n-r_n,
$$
$$
M_n=\binom{n}{\le d_n},
\qquad
N_n=2^n,
$$
and
$$
\mathfrak m_n^*
\mathfrak m^*(D_n,r_n)
\max_{1\le s\le r_n}
\frac{2^s-1}{\binom{D_n}{s}}.
$$
Theorem 10.1. General off-origin slack criterion
Assume:
there exists \(\varepsilon>0\) such that
$$
\frac{r_n}{n}>\frac12+\varepsilon
$$
for all sufficiently large (n);
\(\mathfrak m_n^*\to0\).
Then, for uniformly random \(G_n:{0,1}^n\to{\pm1}\), with high probability,
$$
\eta_{D_n}(G_n)
\ge
\frac{1-\tau_n}{1+\tau_n}\cdot\frac1{\mathfrak m_n^*}-1,
$$
where
$$
\tau_n=
O\left(\sqrt{\frac{M_nn}{N_n}}\right)
2^{-\Omega(n)}.
$$
In particular, if
$$
\frac{\tau_n}{\mathfrak m_n^*}=o(1),
$$
then
$$
\eta_{D_n}(G_n)
\ge
\frac1{\mathfrak m_n^*}-1-o(1).
$$
Proof
Normalize
$$
G_\varnothing=1
$$
by multiplying (G) globally by \(G_\varnothing\). The nonempty signs remain independent uniform signs.
Let \(\nu\) be any probability measure on nonempty subsets, and set
$$
\theta_T=\nu_TG_T.
$$
Let (h) be its upward-zeta transform. Let \(\theta^{\le r_n}\) and \(\theta^{>r_n}\) be defined as above. By Lemma 6.1,
$$
|\theta^{\le r_n}|_1
\le
\mathfrak m_n^*B_{D_n,G}(\nu).
$$
Now pass to complement variables. Define
$$
q(U)=(-1)^{|U|}\theta^{>r_n}_{U^c},
\qquad
U\ne[n].
$$
By Lemma 7.1,
$$
q\in W_{\le d_n}.
$$
Define
$$
\xi_U=(-1)^{|U|}G_{U^c},
\qquad
\mu_U=\nu_{U^c}.
$$
Then \(\xi\) is a uniform random sign vector on \(\Omega_n^\circ\), \(\mu\) is a probability measure on \(\Omega_n^\circ\), and
$$
\xi\cdot\mu\in \mathcal C_\xi.
$$
Moreover,
$$
|q-\xi\cdot\mu|_1
|\theta^{>r_n}-\theta|_1
|\theta^{\le r_n}|_1
\le
\mathfrak m_n^*B_{D_n,G}(\nu).
$$
By assumption (1),
$$
d_n=n-r_n<
\left(\frac12-\varepsilon\right)n
$$
for all sufficiently large (n). Therefore
$$
M_n/N_n\le2^{-\alpha n}
$$
for some \(\alpha>0\). By Lemma 9.1, with high probability,
$$
|\Pi_{W_{\le d_n}}\xi|_\infty\le\tau_n,
$$
where
$$
\tau_n=O\left(\sqrt{\frac{M_nn}{N_n}}\right)=2^{-\Omega(n)}.
$$
On this high-probability event, Lemma 8.1 gives
$$
\operatorname{dist}_{\ell^1}(W_{\le d_n},\mathcal C_\xi)
\ge
\frac{1-\tau_n}{1+\tau_n}.
$$
Thus, uniformly for every \(\nu\),
$$
\mathfrak m_n^*B_{D_n,G}(\nu)
\ge
\frac{1-\tau_n}{1+\tau_n}.
$$
Equivalently,
$$
B_{D_n,G}(\nu)
\ge
\frac{1-\tau_n}{1+\tau_n}\cdot\frac1{\mathfrak m_n^*}.
$$
Since
$$
A_G(\nu)\ge -1,
$$
Proposition 5.1 yields
$$
\eta_{D_n}(G_n)
\min_\nu(A_G(\nu)+B_{D_n,G}(\nu))
\ge
-1+
\frac{1-\tau_n}{1+\tau_n}\cdot\frac1{\mathfrak m_n^*}.
$$
This proves the theorem. \(\square\)
Corollary 10.2. Saturation criterion
Under the assumptions of Theorem 10.1, if
$$
\frac1{\mathfrak m_n^*}\to\infty,
$$
then
$$
\Pr(\gamma_{D_n}(G_n)=1)\to1.
$$
Proof
Theorem 10.1 gives
$$
\eta_{D_n}(G_n)\to\infty
$$
with high probability. In particular,
$$
\eta_{D_n}(G_n)\ge1
$$
with high probability. The empty point has margin exactly (1) by choosing
$$
a_\varnothing=G_\varnothing.
$$
Hence the full margin satisfies
$$
\gamma_{D_n}(G_n)\ge1.
$$
Since always
$$
\gamma_{D_n}(G_n)\le1,
$$
we get
$$
\gamma_{D_n}(G_n)=1
$$
with high probability. \(\square\)

## 11. Linear-degree theorem and optimal off-origin slack
Let
$$
H_2(t)=-t\log_2t-(1-t)\log_2(1-t)
$$
be the binary entropy function. Let (\rho_\in(1/2,1)) be the unique solution of
$$
H_2(\rho_*)=\rho_*.
$$
Since (H_2(t)-t) is strictly decreasing on ((1/2,1)), positive at \(t=1/2\), and negative at \(t=1\), this solution is unique. Numerically,
$$
\rho_*=0.7729078047\ldots,
\qquad
\frac1{2\rho_*}=0.6469076867\ldots.
$$
Theorem 11.1. Optimal off-origin slack in the linear regime
Let \(D_n\) be an integer sequence satisfying
$$
0<\liminf_{n\to\infty}\frac{D_n}{n}
\le
\limsup_{n\to\infty}\frac{D_n}{n}
<\infty,
$$
and
$$
\liminf_{n\to\infty}\frac{D_n}{n}>
\frac1{2\rho_*}.
$$
Then, for uniformly random
$$
G_n:{0,1}^n\to{\pm1},
$$
one has, with high probability,
$$
\eta_{D_n}(G_n)=D_n-1-o(1).
$$
Consequently,
$$
\Pr(\gamma_{D_n}(G_n)=1)\to1.
$$
Proof
Let
$$
c_-=\liminf_{n\to\infty}\frac{D_n}{n}.
$$
By hypothesis,
$$
c_->\frac1{2\rho_*}.
$$
Choose \(c_0\) such that
$$
\frac1{2\rho_*}<c_0<c_-.
$$
Then, for all sufficiently large (n),
$$
D_n\ge c_0 n.
$$
Choose \(\beta\) satisfying
$$
\frac12<\beta<\min(1,\rho_*c_0).
$$
Set
$$
r_n=\lfloor\beta n\rfloor.
$$
Then
$$
r_n\le n
$$
for all large (n). Since \(\rho_*<1\),
$$
\beta<\rho_*c_0<c_0,
$$
and therefore
$$
r_n\le D_n
$$
for all large (n). Also,
$$
\frac{r_n}{n}\to\beta>\frac12.
$$
Choose \(\rho_0\) such that
$$
\frac{\beta}{c_0}<\rho_0<\rho_*.
$$
Then, for all sufficiently large (n),
$$
\frac{r_n}{D_n}\le \rho_0.
$$
We estimate
$$
\mathfrak m^*(D_n,r_n)
\max_{1\le s\le r_n}
\frac{2^s-1}{\binom{D_n}{s}}.
$$
At \(s=1\),
$$
\frac{2^1-1}{\binom{D_n}{1}}
\frac1{D_n}.
$$
For \(s\ge2\), define
$$
\alpha_s=\frac{2^s}{\binom{D_n}{s}}.
$$
Then
$$
\frac{2^s-1}{\binom{D_n}{s}}\le \alpha_s.
$$
Moreover,
$$
\frac{\alpha_{s+1}}{\alpha_s}
\frac{2(s+1)}{D_n-s}.
$$
This ratio is increasing in (s). Hence the sequence \(\alpha_s\) decreases and then increases, so on the interval \(2\le s\le r_n\) its maximum is attained at one of the endpoints \(s=2\) or \(s=r_n\).
At \(s=2\),
$$
\alpha_2
\frac4{\binom{D_n}{2}}
O(D_n^{-2})
<
D_n^{-1}
$$
for all sufficiently large (n).
It remains to control \(s=r_n\). Put
$$
t_n=\frac{r_n}{D_n}.
$$
We have
$$
t_n\le \rho_0<\rho_*.
$$
Since (D_n=O(n)) by hypothesis and \(r_n\sim\beta n\), there is a constant \(t_0>0\) such that
$$
t_n\ge t_0
$$
for all sufficiently large (n). Therefore \(t_n\) lies in a compact subinterval of (\(0,\rho_*\)). Hence there exists \(\delta>0\) such that
$$
H_2(t_n)-t_n\ge \delta
$$
for all sufficiently large (n).
By Stirling's formula, uniformly in this compact range,
$$
\binom{D_n}{r_n}
2^{D_nH_2(t_n)+o(n)}.
$$
Thus
$$
\frac{2^{r_n}}{\binom{D_n}{r_n}}
2^{D_nt_n-D_nH_2(t_n)+o(n)}
2^{-D_n(H_2(t_n)-t_n)+o(n)}
2^{-\Omega(n)}.
$$
Consequently,
$$
\mathfrak m^*(D_n,r_n)=\frac1{D_n}
$$
for all sufficiently large (n).
The hypotheses of Theorem 10.1 are satisfied. Moreover,
$$
\tau_n=2^{-\Omega(n)}.
$$
Since (D_n=O(n)),
$$
D_n\tau_n=o(1).
$$
Therefore Theorem 10.1 gives
$$
\eta_{D_n}(G_n)
\ge
\frac{1-\tau_n}{1+\tau_n}D_n-1
D_n-1-o(1).
$$
It remains to prove the matching upper bound. Normalize \(G_\varnothing=1\). The singleton signs
$$
G_{{1}},\dots,G_{{n}}
$$
are independent uniform signs. With probability \(1-2^{-n}\), at least one singleton has sign (-1). Choose such an (i).
For any feasible polynomial with
$$
a_\varnothing=1,
$$
we have
$$
p(1_{{i}})=1+a_{{i}},
\qquad
|a_{{i}}|\le D_n.
$$
Since \(G_{{i}}=-1\), the margin at this point is
$$
G_{{i}}p(1_{{i}})
-(1+a_{{i}})
\le
D_n-1.
$$
Thus, with high probability,
$$
\eta_{D_n}(G_n)\le D_n-1.
$$
Combining the lower and upper bounds,
$$
\eta_{D_n}(G_n)=D_n-1-o(1)
$$
with high probability.
Since \(D_n\to\infty\), this implies
$$
\eta_{D_n}(G_n)\ge1
$$
with high probability. Therefore
$$
\gamma_{D_n}(G_n)=1
$$
with high probability. \(\square\)

## 12. Homogeneous-form version
Theorem 11.1 has an equivalent homogeneous formulation.
Let \(D_n\) be a linear degree sequence satisfying
$$
0<\liminf_{n\to\infty}\frac{D_n}{n}
\le
\limsup_{n\to\infty}\frac{D_n}{n}
<\infty
$$
and
$$
\liminf_{n\to\infty}\frac{D_n}{n}>
\frac1{2\rho_*}.
$$
Then, with high probability over uniformly random \(G_n\), there exists a homogeneous form
$$
F\in \mathbb{R}[X_0,\dots,X_n]_{D_n}
$$
whose homogeneous coefficients all lie in ([-1,1]), such that
$$
G_n(0,\dots,0)F(1,0,\dots,0)=1
$$
and
$$
G_n(x)F(1,x)
\ge
D_n-1-o(1)
$$
for every nonzero
$$
x\in{0,1}^n.
$$
In particular,
$$
G_n(x)F(1,x)>0
\qquad
\forall x\in{0,1}^n
$$
with high probability.
This follows directly from Theorem 11.1 and the exact realization of the coefficient box by homogeneous forms from Section 2.

## 13. A pseudorandom variant
The proof uses randomness only through the projection estimate
$$
|\Pi_{W_{\le d}}\xi|_\infty=o(1).
$$
This estimate also holds for sufficiently high-wise independent signs.
Proposition 13.1. (O(n))-wise independence suffices for the projection step
Fix \(\varepsilon>0\), and let
$$
d\le\left(\frac12-\varepsilon\right)n.
$$
Let
$$
\xi\in{\pm1}^{\Omega_n^\circ}
$$
be (k)-wise independent with
$$
k\ge C_\varepsilon n
$$
for a sufficiently large constant \(C_\varepsilon\). Then
$$
|\Pi_{W_{\le d}}\xi|_\infty=o(1)
$$
with high probability.
Consequently, the saturation and off-origin slack conclusions above remain valid under any sign distribution for which, after normalizing the origin, the induced sign vector
$$
\left((-1)^{|U|}G_{U^c}\right)_{U\in\Omega_n^\circ}
$$
is (O(n))-wise independent.
Proof
Let (P') be the projection matrix onto \(W_{\le d}\). As in Lemma 9.1,
$$
\sum_y(P'_{xy})^2=P'{xx}\le C_0\frac{M}{N},
$$
where
$$
M=\binom{n}{\le d},
\qquad
N=2^n.
$$
Since
$$
d\le\left(\frac12-\varepsilon\right)n,
$$
there is \(\alpha>0\) such that
$$
M/N\le2^{-\alpha n}.
$$
For fixed (x),
$$
(\Pi\xi)(x)=\sum_yP'_{xy}\xi_y.
$$
Because \(\xi\) is (k)-wise independent, its moments up to order (k) agree with those of fully independent signs. For even (k), the Khintchine moment bound gives
$$
\mathbb{E}|(\Pi\xi)(x)|^k
\le
(C\sqrt{k})^k
\left(\sum_y(P'_{xy})^2\right)^{k/2}.
$$
Thus
$$
\mathbb{E}|(\Pi\xi)(x)|^k
\le
(C\sqrt{k})^k
\left(C_0\frac{M}{N}\right)^{k/2}.
$$
Let
$$
t=A\sqrt{\frac{Mn}{N}}.
$$
By Markov's inequality,
$$
\Pr(|(\Pi\xi)(x)|>t)
\le
\left(\frac{C\sqrt{k}}{A\sqrt n}\right)^k.
$$
Taking
$$
k=C_1n
$$
and choosing \(A,C_1\) so that the right-hand side is at most \(2^{-3n}\), a union bound over at most \(2^n\) points gives
$$
\Pr(|\Pi\xi|_\infty>t)\le2^{-2n}.
$$
Since
$$
t=A\sqrt{\frac{Mn}{N}}=o(1),
$$
the result follows. \(\square\)

## 14. Toward integer and ternary lifts
The results in this paper are over real coefficients. They do not assert the existence of integer or ternary homogeneous coefficient representations.
Let
$$
Z_{T,S}=\mathbf 1_{S\subseteq T}
$$
be the Boolean zeta matrix, restricted to columns \(|S|\le D\). A rounding theorem converting real coefficients inside the box to integer coefficients while preserving signs would imply ternary homogeneous lifts: every integer coefficient
$$
b_S\in[-\binom D{|S|},\binom D{|S|}]
$$
can be written as a sum of \(\binom D{|S|}\) elements of \({-1,0,1}\), which can then be distributed among the homogeneous monomials reducing to \(x_S\).
The optimal off-origin slack
$$
D-1-o(1)
$$
shows that the real solution has large non-origin margin. However, this margin is only linear in (D), and it is not by itself a rounding theorem. Universal, independent, or level-wise rounding estimates are not supplied by the present argument. A discrete version would require new correlated rounding methods or a direct lattice construction.

## 15. Scope and limitations
The main theorem is a real-coefficient result. It does not imply integer, ternary, or rounded homogeneous coefficient representations.
The constant
$$
\frac1{2\rho_*}=0.6469076867\ldots
$$
is a threshold of the present method, not claimed to be optimal. The proof requires a truncation level
$$
r>n/2
$$
so that the complementary polynomial space has exponentially small dimension relative to \(2^n\), and also requires
$$
r/D<\rho_*
$$
so that the sharp weighted-zeta localization parameter
$$
\mathfrak m^*(D,r)
\max_{1\le s\le r}
\frac{2^s-1}{\binom D s}
$$
is dominated by the singleton level (1/D). These two inequalities combine to force
$$
D>\frac n{2\rho_*}.
$$
The theorem is stated in the linear regime (D_n=\Theta(n)). This is the regime in which the method yields the asymptotically sharp off-origin margin
$$
D_n-1-o(1).
$$
For more rapidly growing \(D_n\), the general criterion of Theorem 10.1 remains valid, but the additive error term must be tracked separately.
Classical random threshold-degree results concern unbounded real coefficients. The present theorem concerns a specific bounded coefficient body arising from homogeneous height-one lifts. It is therefore a bounded-coefficient random representation theorem.

## 16. Summary of the argument
The proof may be summarized as follows.
A homogeneous degree-(D), height-one real lift induces exactly the multilinear box
$$
|a_S|\le \binom D{|S|}.
$$
The off-origin margin has the exact dual form
$$
\eta_D(G)
\min_\nu
\bigl(A_G(\nu)+B_{D,G}(\nu)\bigr),
$$
where \(B_{D,G}\) is a weighted upward-zeta norm.
For every dual measure \(\nu\), the low-level Möbius inverse of
$$
\theta_T=\nu_TG_T
$$
satisfies
$$
|\theta^{\le r}|_1
\le
\mathfrak m^*(D,r)B_{D,G}(\nu).
$$
Removing this low-level part leaves high-zeta data. After complementing subsets and applying a parity sign, this high-zeta data becomes a low-degree polynomial of degree at most (n-r).
If
$$
r>n/2+\varepsilon n,
$$
then the degree-((n-r)) polynomial space has exponentially small dimension relative to the cube. A random signed simplex is then \(\ell^1\)-separated from that subspace.
Therefore
$$
\mathfrak m^*(D,r)B_{D,G}(\nu)\ge1-o(1)
$$
uniformly in \(\nu\).
In the linear regime \(D=cn\), with
$$
c>\frac1{2\rho_*},
$$
one can choose \(r>n/2\) with
$$
r/D<\rho_*.
$$
In this range,
$$
\mathfrak m^*(D,r)=\frac1D.
$$
Hence
$$
B_{D,G}(\nu)\ge D-o(1)
$$
uniformly in \(\nu\), and since
$$
A_G(\nu)\ge-1,
$$
one obtains
$$
\eta_D(G)\ge D-1-o(1).
$$
A matching upper bound (D-1) holds with high probability because, after normalizing \(G_\varnothing=1\), at least one singleton has sign (-1) with high probability.
This proves
$$
\eta_{D_n}(G_n)=D_n-1-o(1)
$$
and therefore
$$
\gamma_{D_n}(G_n)=1
$$
with high probability.

## References
[AF93] N. Alon and Z. Füredi, Covering the cube by affine hyperplanes, European Journal of Combinatorics 14 (1993), 79--83.
[BCPS18] A. Bishnoi, P. L. Clark, A. Potukuchi, and J. R. Schmitt, On zeros of a polynomial in a finite grid, Combinatorics, Probability and Computing 27 (2018), 310--333.
[BV19] P. Baldi and R. Vershynin, Polynomial threshold functions, hyperplane arrangements, and random tensors, SIAM Journal on Mathematics of Data Science 1 (2019), 699--729.
[Mur71] S. Muroga, Threshold Logic and Its Applications, Wiley-Interscience, 1971.
[OD14] R. O'Donnell, Analysis of Boolean Functions, Cambridge University Press, 2014.
[OS08] R. O'Donnell and R. A. Servedio, Extremal Properties of Polynomial Threshold Functions, Journal of Computer and System Sciences 74 (2008), 298--312.