\section{Effective realization of the quadratic margins}\label{app:three}

We prove Proposition~\ref{short:prop:quadratic_matrix}. Throughout this
appendix, \(p=2m+1\), \(n=p-g\), and \(N=n(n-1)/2\).
The quadratic character \(\chi\) and its interval bound \(C_\chi\)
are as defined in Section~\ref{sec:three-balance}, with
\(H=C_\chi+g+2\le m/12\).
Each value of the quadratic modulo \(p\) offers two column sums. We must choose between
them so that their total matches the row sums and the chosen
diagonal still fits. Equal totals alone do not guarantee such a matrix.
We first quantify the room required for the diagonal, then show that
lifting the smallest columns leaves enough room in every cut.

\subsection{Room for the chosen diagonal}
We need enough spare capacity in each matrix cut to accommodate the
chosen diagonal. For each integer \(0\le k\le n\), define the margin gap
\begin{equation}\label{short:eq:galegap}
 G_k=\sum_{i=0}^{n-1}\min(Q_i,k)-\frac{k(2n-k-1)}2.
\end{equation}
The subtracted term is the sum of the largest \(k\) desired row sums;
the next lemma shows how a lower bound on this gap absorbs the
diagonal corrections.

\begin{lemma}\label{short:lem:diagonal}
Suppose the integers \(Q_i\) satisfy \(\sum_iQ_i=N\) and \(1\le Q_i\le n-2\).
Let \(\alpha_i\in\{0,1\}\) with \(\alpha_0=0\). If
\[
 G_k\ge n\qquad\text{whenever }\min_iQ_i\le k\le\max_iQ_i,
\]
then a binary matrix with row sums \(i\), column sums \(Q_i\),
and diagonal \(\alpha_i\) exists.
\end{lemma}
\begin{proof}
Reserve the diagonal ones, subtract \(\alpha_i\) from row and column \(i\),
and forbid all diagonal positions in the remaining matrix.
The residual demands are nonnegative and have the same total.
The integral-flow criterion for matrices with a forbidden diagonal
\cite[p.~832, equation~(2)]{fulkerson}, applied with rows and columns
interchanged, requires the following inequality for every
\(I\subseteq\{0,\ldots,n-1\}\):
\[
 \sum_{i\in I}(i-\alpha_i)
 \le \sum_j\min(Q_j-\alpha_j,k-\ind_{\{j\in I\}})
 \qquad (k=|I|).
\]
Moving the diagonal corrections to the left gives the equivalent condition
\begin{equation}\label{short:eq:diagonalcut}
 \sum_{i\in I}i
 +\#\{i\in I:\alpha_i=0,\ Q_i\ge k\}
 +\#\{i\notin I:\alpha_i=1,\ Q_i\le k\}
 \le\sum_i\min(Q_i,k).
\end{equation}
For \(k\) in the stated range the two counts sum to at most \(n\),
so the hypothesis verifies the cut.

If \(k<\min_iQ_i\), the second count vanishes and the first is at most \(k\).
Here \(G_k=k(k+1)/2\ge k\), so the cut also holds.
If \(k>\max_iQ_i\), the first count vanishes and the right side is \(N\).
The cut follows from
\(\sum_{i\notin I}\alpha_i\le\sum_{i\notin I}i\), since \(\alpha_0=0\) and
\(\alpha_i\le1\le i\) for \(i\ge1\).
The empty set satisfies the criterion as well. Integral flow gives the
required residual matrix, and restoring the diagonal completes the proof.
\end{proof}

\subsection{Two representatives and one-sided counts}
The balancing step will lift the smallest low representatives from
\eqref{short:eq:low}--\eqref{short:eq:lift}, so we need bounds on how
many are available in each parity class. Completing the square
expresses their multiplicities through the quadratic character,
whose interval bounds will control the cumulative counts. For counting purposes,
extend \(f(i)=i(i+3)/2\), \(r_i(d)=(f(i)+d)\bmod p\), and
\(L_i(d)=\lceil r_i(d)/2\rceil\) to \(0\le i<p\); the construction
retains only \(0\le i<n\). We omit \(d\) when the shift is fixed.
Over all \(p\) indices, the multiplicity of a residue
\(r\in\{0,\ldots,p-1\}\) is
\(1+\chi(8r+9-8d)\), by completing the square. Each multiplicity is at most two.
Let \(g_{\rm e}\) and \(g_{\rm o}\) count the even and odd output residues
among the removed indices \(n,\ldots,p-1\), so
\(g_{\rm e}+g_{\rm o}=g\).
Let \(C_{\rm e}(t)\) and \(C_{\rm o}(t)\) count retained low values at most
\(t\) in each parity class. For \(0\le t\le m\),
\begin{align}
 \lfloor t\rfloor+1-C_\chi-g_{\rm e}
 &\le C_{\rm e}(t)\le\lfloor t\rfloor+1+C_\chi,\notag\\
 \lfloor t\rfloor-C_\chi-g_{\rm o}
 &\le C_{\rm o}(t)\le\lfloor t\rfloor+C_\chi.
 \label{short:eq:counts}
\end{align}
Indeed, the even residues \(r=2\ell\) produce
\(\chi(16\ell+9-8d)\), and the odd residues \(r=2\ell-1\) produce
\(\chi(16\ell+1-8d)\). Since \(16\) is a square, each sum is a translated
character sum on an interval. Deleting inputs can only decrease a count.

The sum of all low values has a useful additional estimate.
For integer \(0\le t<m\), the full count with \(L_i\le t\) is
\(2t+1+E_t\), where
\[
 E_t=\sum_{r=0}^{2t}\chi(8r+9-8d),\qquad |E_t|\le C_\chi.
\]
Factoring the nonzero coefficient \(8\) reduces this to another interval sum.
Consequently,
\[
 S_{\rm full}:=\sum_{i=0}^{p-1}L_i
 =mp-\sum_{t=0}^{m-1}(2t+1+E_t),\qquad
 |S_{\rm full}-m(m+1)|\le mC_\chi.
\]
Put \(S(d)=\sum_{i=0}^{n-1}L_i(d)\), \(D(d)=N-S(d)\), and
\(\delta_0=g(g-1)/(2m)\). Write \(S,D\) when the shift is fixed.
The deleted low values have sum between zero and \(mg\). Expanding
\(N=(2m+1-g)(2m-g)/2\) therefore gives
\begin{equation}\label{short:eq:deficit}
 m-2g+\delta_0-C_\chi\le D/m\le m-g+\delta_0+C_\chi.
\end{equation}

\subsection{Balancing the total exactly}
The remaining deficit must be a sum of the two available increments,
\(m\) and \(m+1\). We vary the even shift \(d\) until \(D(d)\) modulo
\(m\) enters an interval that gives admissible numbers of lifts,
using a walk with bounded increments to guarantee such a shift.

For \(t\in\{0,\ldots,p-1\}\), let
\(c_t(d)=|\{i:0\le i<n,\ r_i(d)=t\}|\le2\).
Increasing \(d\) by two raises each low value by one, except that
residues \(p-2\) and \(p-1\) wrap to zero and one.
It follows that
\[
 S(d+2)-S(d)=n-(m+1)c_{p-2}(d)-mc_{p-1}(d),
\]
and hence
\begin{equation}\label{short:eq:walk}
 D(d+2)-D(d)\equiv g-1+c_{p-2}(d)\pmod m.
\end{equation}
The consecutive even shifts in \([m/2,3m/2]\) have
\(J=\lfloor3m/4\rfloor-\lceil m/4\rceil\ge m/2-2\) steps.
Lift the residues \(D(d)\bmod m\) to an increasing walk whose increments
lie in \([g-1,g+1]\), as permitted by~\eqref{short:eq:walk}.
Its total increase is at least \(4J\ge2m-8>m\).
Also \(g+1<m/3\), by~\eqref{short:eq:effective_condition}.
The next translated left endpoint of \([m/3,2m/3]\) is at most \(m\)
away, and the first crossing overshoots it by less than \(m/3\).
Fig.~\ref{fig:residue-walk} shows why the crossing stays in the
target interval. Thus an even shift satisfies
\begin{equation}\label{short:eq:xy}
 Y=D(d)\bmod m\in[m/3,2m/3],\qquad
 K=\lfloor D(d)/m\rfloor,\qquad X=K-Y.
\end{equation}
\begin{figure}[htbp]
\centering\input{figures/residue_walk.tex}
\caption{Why a suitable shift exists in~\eqref{short:eq:walk}. Divide the
lifted values of \(D(d)\bmod m\) by \(m\). Consecutive values advance
by less than \(1/3\), and the walk travels more than one period. It
therefore enters a translate of \([1/3,2/3]\). The orange point marks
the first crossing in a schematic walk; the plotted values illustrate
the interval argument rather than a particular degree certificate.}
\label{fig:residue-walk}
\end{figure}
\FloatBarrier

In particular,
\begin{equation}\label{short:eq:exactbalance}
 D=mX+(m+1)Y
\end{equation}
holds exactly. Since \(g<m\), one has \(\delta_0\le g\).
Equation~\eqref{short:eq:deficit} gives
\begin{equation}\label{short:eq:k_bounds}
 m-2g+\delta_0-C_\chi-1\le K\le m-g+\delta_0+C_\chi.
\end{equation}
Hence \(0<X\le2m/3+C_\chi\).
The odd class has at least \(m-C_\chi-g\) indices by~\eqref{short:eq:counts},
which exceeds this upper bound for \(X\).
The even class after excluding index zero has at least \(m-C_\chi-g>2m/3\)
indices. These inequalities follow from \(C_\chi+g+2\le m/12\).

Choose the \(X\) smallest low values among indices with odd \(r_i\),
and the \(Y\) smallest among indices with even \(r_i\) and index different
from zero. Ties may be resolved arbitrarily.
Set \(\epsilon_i=1\) at these indices and \(0\) elsewhere, and define
\begin{equation}\label{short:eq:finaldegrees}
 Q_i=L_i+\epsilon_i(m+1-\alpha_i^0),\qquad
 \alpha_i=\begin{cases}\alpha_i^0,&\epsilon_i=0,\\1-\alpha_i^0,&\epsilon_i=1.\end{cases}
\end{equation}
Then \(2Q_i-\alpha_i=r_i+p\epsilon_i\), and~\eqref{short:eq:exactbalance} gives
\(\sum_iQ_i=N\).
Moreover, \(r_0=d\) is even, so
\begin{equation}\label{short:eq:zeroindex}
 \alpha_0=0,\qquad Q_0=d/2\in[m/4,3m/4].
\end{equation}
This exclusion respects the zero row sum at index zero.

\subsection{Bounds for the column tails}
The selection concentrates the columns. In the ideal case of uniform
low values and \(X=m-Y\), its two classes occupy the intervals
\([Y,Y+m]\) and \([m-Y,2m-Y]\), shown in
Fig.~\ref{short:fig:distribution}. We bound the finite errors through
the two tails to verify that this concentration leaves enough room
for the chosen diagonal. For a real number \(x\), write
\(x_+=\max\{x,0\}\) for its \emph{positive part}.

\begin{figure}[htb]
\centering
\begin{tikzpicture}[font=\small,>=Latex]
\begin{scope}[x=2.6cm,y=1.05cm]
\node[anchor=west] at (-.05,3.45) {(a) Ideal densities, $Y/m=1/3$};
\fill[blue!12] (1/3,0)--(1/3,1)--(2/3,1)--(2/3,2)
 --(4/3,2)--(4/3,1)--(5/3,1)--(5/3,0)--cycle;
\draw[blue!70!black,thick] (1/3,0)--(1/3,1)--(2/3,1)--(2/3,2)
 --(4/3,2)--(4/3,1)--(5/3,1)--(5/3,0);
\draw[dashed,thick] (0,1)--(2,1);
\draw[->] (0,0)--(2.17,0) node[right] {degree$/m$};
\draw[->] (0,0)--(0,2.45) node[above] {density};
\foreach \x/\lab in {0/0,.33333/{1/3},.66667/{2/3},1/1,1.33333/{4/3},1.66667/{5/3},2/2}
 {\node[below,font=\footnotesize] at (\x,-.05) {$\lab$};}
\node[left] at (0,1) {1};\node[left] at (0,2) {2};
\node[blue!70!black] at (1,2.28) {columns};
\node at (1.9,1.32) {rows};
\end{scope}
\begin{scope}[shift={(8.05,0)},x=3.7cm,y=2.2cm]
\node[anchor=west] at (-.05,1.6466) {(b) The room in the cut at $k=m$};
\fill[blue!15] (0,0)--(1,1)--(2/3,1/3)--(1/3,0)--cycle;
\draw[dashed,thick] (0,0)--(1,1);
\draw[blue!70!black,thick] (0,0)--(1/3,0)--(2/3,1/3)--(1,1);
\draw[->] (0,0)--(1.18,0) node[right] {$x$};
\draw[->] (0,0)--(0,1.18) node[above] {cumulative mass};
\foreach \x/\lab in {0/0,.33333/{1/3},.66667/{2/3},1/1}
 {\node[below,font=\footnotesize] at (\x,-.025) {$\lab$};}
\node[left] at (0,1) {1};
\node[font=\footnotesize] at (.52,.35) {$2/9$};
\end{scope}
\node[align=center] at (6.2,-1.1)
 {$\text{ideal gap}/m^2=\displaystyle\int_0^1
  \bigl(x-(x-\tfrac13)_+-(x-\tfrac23)_+\bigr)\,dx=2/9$};
\end{tikzpicture}
\caption{How concentration of the columns creates room for the chosen
diagonal. In (a), the ideal column measure is the sum of uniform densities
on \([1/3,4/3]\) and \([2/3,5/3]\); the dashed row measure is uniform
on \([0,2]\). The horizontal coordinate is a row or column sum divided
by \(m\); both measures have mass two and mean one. In (b), their
cumulative masses up to the normalized value \(x\le1\) enclose an area
of \(2/9\). Multiplying this
area by \(m^2\) gives the ideal gap at the cut \(k=m\).
The finite construction requires the error estimates below to retain
enough of this gap.}
\label{short:fig:distribution}
\end{figure}
\FloatBarrier

Put
\begin{equation}\label{short:eq:abq}
 \ell_1=Y-2H,\qquad \ell_2=m-Y-2H,\qquad \rho=m/6.
\end{equation}
Both \(\ell_1\) and \(\ell_2\) are at least \(\rho\).
An unselected low value with odd \(r_i\) is at least \(X-C_\chi\), by the upper
bound in~\eqref{short:eq:counts}; an eligible unselected low value with even \(r_i\) is at least
\(Y-C_\chi-1\). Equations~\eqref{short:eq:k_bounds} and~\eqref{short:eq:abq} imply
\[
 X-C_\chi\ge m-Y-2g-2C_\chi-1\ge\ell_2,\qquad Y-C_\chi-1\ge\ell_1.
\]
The lifted columns are at least \(m+1\), and~\eqref{short:eq:zeroindex}
handles index zero. Thus \(Q_i\ge\rho\) for every \(i\).

Let \(\widetilde C_{\rm e}\) exclude index zero from \(C_{\rm e}\).
The lower bounds in~\eqref{short:eq:counts} imply, for \(0\le t\le m\),
\begin{equation}\label{short:eq:low_tail_counts}
 C_{\rm o}(t)\ge t-1-C_\chi-g_{\rm o},\qquad
 \widetilde C_{\rm e}(t)\ge t-1-C_\chi-g_{\rm e}.
\end{equation}
Therefore every lifted column with odd \(r_i\) is at most \(U_{\rm o}\),
and every lifted column with even \(r_i\) is at most \(U_{\rm e}\), where
\[
 U_{\rm o}=m+X+C_\chi+g_{\rm o}+1,\qquad
 U_{\rm e}=m+Y+C_\chi+g_{\rm e}+2.
\]
For example, the \(X\)-th low value in the odd-residue class is at most \(X+C_\chi+g_{\rm o}+1\)
by~\eqref{short:eq:low_tail_counts}; the same reasoning applies to the even class.
Using~\eqref{short:eq:k_bounds} gives
\begin{align}
 n-U_{\rm o}&\ge Y-\delta_0-2C_\chi-g_{\rm o}\ge\ell_1,\notag\\
 n-U_{\rm e}&=m-Y-g-C_\chi-g_{\rm e}-1\ge\ell_2.
 \label{short:eq:upper_columns}
\end{align}
Here \(\delta_0\le g\) and \(g_{\rm e},g_{\rm o}\le g\).
Unlifted columns are at most \(m<n-\rho\). We conclude that
\begin{equation}\label{short:eq:interior}
 \rho\le Q_i\le n-\rho\qquad(0\le i<n).
\end{equation}
Since \(m\ge150\), the columns are integers between one and \(n-2\).

For real \(t\), put \(C_Q(t)=\#\{i:Q_i\le t\}\).
For \(0\le t\le m\), lifted values do not contribute, and selection of
the smallest values gives
\[
 C_Q(t)=(C_{\rm o}(t)-X)_+
       +(\widetilde C_{\rm e}(t)-Y)_+
       +\ind_{\{Q_0\le t\}}.
\]
The preceding estimates yield
\begin{equation}\label{short:eq:lower_cdf}
 C_Q(t)\le(t-\ell_1)_++(t-\ell_2)_+
                 +\ind_{\{m/4\le t\}}.
\end{equation}

For \(k\ge m\), only lifted columns contribute to \(\sum_i(Q_i-k)_+\).
In a class where the smallest \(T\) low values were selected, the number
of selected values above a real threshold \(t\) is \((T-C(t))_+\).
Here \(C=C_{\rm o}\) for odd residues and
\(C=\widetilde C_{\rm e}\) for eligible even residues.
Integrating~\eqref{short:eq:low_tail_counts} therefore gives
\begin{equation}\label{short:eq:upper_tail}
 \sum_i(Q_i-k)_+
 \le\frac{(U_{\rm o}-k)_+^2}{2}
    +\frac{(U_{\rm e}-k)_+^2}{2}.
\end{equation}
For the even class at \(k=m\), the low-value integration starts at \(-1\).
On \([-1,0]\), its tail count is at most \(Y\), which is bounded by
\(Y+C_\chi+g_{\rm e}+1-t\). Thus~\eqref{short:eq:upper_tail} also holds at that
endpoint. Above \(m\), the low-value tail is zero, and extending the
positive-part bound only increases the integral.

\subsection{Uniform room in the matrix inequalities}
The tail estimates must now give \(G_k\ge n\) throughout the range
required by Lemma~\ref{short:lem:diagonal}. We use the lower and upper
tails through the respective identities
\begin{align}
 G_k&=\frac{k(k+1)}2-\int_0^k C_Q(t)\,dt,\notag\\
 G_k&=\frac{(n-k)(n-k-1)}2-\sum_i(Q_i-k)_+
 \label{short:eq:gap_identities}
\end{align}
from~\eqref{short:eq:galegap} and \(\sum_iQ_i=N\). These forms reduce
the small and large cuts to a common one-variable bound.
For real \(x\in[\rho,m]\), define
\begin{equation}\label{short:eq:cut_function}
 F(x)=\frac{x(x-1)}2
       -\frac{(x-\ell_1)_+^2}{2}-\frac{(x-\ell_2)_+^2}{2}.
\end{equation}
For \(k\le m\), integrating~\eqref{short:eq:lower_cdf} in the first identity
of~\eqref{short:eq:gap_identities} gives
\[
 G_k\ge F(k)+k-(k-m/4)_+\ge F(k).
\]
For \(k\ge m\), use~\eqref{short:eq:upper_columns} and~\eqref{short:eq:upper_tail}
in the second identity to obtain \(G_k\ge F(n-k)\).
When \(\min_iQ_i\le k\le\max_iQ_i\), the relevant argument is in
\([\rho,m]\), by~\eqref{short:eq:interior} and \(n-m=m+1-g<m\).

The minimum of \(F\) on this interval is attained at an endpoint.
Its derivative is initially \(x-1/2>0\), then
\(\min(\ell_1,\ell_2)-1/2>0\), and finally
\(\ell_1+\ell_2-x-1/2\). The last expression decreases, so it can produce
a maximum but cannot produce an interior minimum. At the endpoints,
\begin{align}
 F(\rho)&=m^2/72-m/12,\notag\\
 F(m)&=Y(m-Y)-2mH-4H^2-m/2
       \ge m^2/36-m/2.\label{short:eq:explicit_gaps}
\end{align}
The second estimate uses \(m/3\le Y\le2m/3\) and \(H\le m/12\).
Both expressions are at least \(2m\) when \(m\ge150\).
Thus \(G_k\ge2m\ge n\) for every cut in the occupied column range.
Lemma~\ref{short:lem:diagonal} realizes the margins and diagonal in
\eqref{short:eq:finaldegrees}, proving Proposition~\ref{short:prop:quadratic_matrix}.

\subsection{An explicit threshold}
To verify the hypotheses of Proposition~\ref{short:prop:quadratic_matrix}
for every \(n\ge10\,000\), we combine published bounds on prime gaps
and quadratic-character sums. Dusart~\cite[Theorem~1, p.~55]{dusart1999}
proves that for every \(x\ge3275\) there is a prime
\begin{equation}\label{short:eq:dusart}
 x<p\le x\left(1+\frac1{2\log^2x}\right).
\end{equation}
For the quadratic character modulo a prime \(p>2\),
Lapkova~\cite[Lemma~3A]{lapkova2018} bounds every interval sum.
Her two cases, \(\chi(-1)=1\) and \(\chi(-1)=-1\), have leading
constants \(2/\pi^2\) and \(1/(2\pi)\), respectively.
Both imply the common bound
\begin{equation}\label{short:eq:pv_explicit}
 C_\chi=(0.203\log p+0.947)\sqrt p+1.668.
\end{equation}
The constants for \(\chi(-1)=1\) are \(2/\pi^2,0.9467,1.668\);
those for \(\chi(-1)=-1\) are smaller. All logarithms are natural.

\begin{corollary}\label{short:cor:threshold}
For every integer \(n\ge10\,000\), a prime \(p\ge n+5\) and a binary
matrix satisfying~\eqref{short:eq:target} exist.
\end{corollary}
\begin{proof}
Apply~\eqref{short:eq:dusart} to \(x=n+4\), and put \(g=p-n\) and
\(m=(p-1)/2\). Since \(\log(n+4)>9\),
\[
 \frac gn\le\frac4{10\,000}+\frac{1.0004}{162}
 <0.006576,\qquad p<1.01n.
\]
The functions \(\log(1.01n)/\sqrt n\) and \(1/\sqrt n\) decrease for
\(n\ge10\,000\). Using \(\log10\,100<10\) and \(\sqrt{1.01}<1.01\)
in~\eqref{short:eq:pv_explicit},
\[
 \frac{C_\chi}{n}
 <\frac{1.01(2.03+0.947)}{100}+\frac{1.668}{10\,000}
 =0.0302345.
\]
Consequently
\[
 \frac{C_\chi+g+2}{n}<0.0302345+0.006576+0.0002
 =0.0370105<\frac1{24}.
\]
Since \(g\ge5\), one has \(m>n/2\), so \(C_\chi+g+2<m/12\).
Also \(m\ge150\). Proposition~\ref{short:prop:quadratic_matrix} applies.
\end{proof}