\documentclass[11pt,a4paper]{amsart}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{newtxtext,newtxmath}
\usepackage[margin=1in]{geometry}
\usepackage{microtype,mathtools,booktabs,array}
\usepackage{enumitem}
\usepackage[hidelinks]{hyperref}
\usepackage{aliascnt}
\usepackage[capitalise,nameinlink,noabbrev]{cleveref}
\crefname{appendix}{Appendix}{Appendices}
\Crefname{appendix}{Appendix}{Appendices}
\allowdisplaybreaks[2]
\emergencystretch=2em
\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newaliascnt{lemma}{theorem}
\newtheorem{lemma}[lemma]{Lemma}
\aliascntresetthe{lemma}
\newaliascnt{proposition}{theorem}
\newtheorem{proposition}[proposition]{Proposition}
\aliascntresetthe{proposition}
\newaliascnt{corollary}{theorem}
\newtheorem{corollary}[corollary]{Corollary}
\aliascntresetthe{corollary}
\newaliascnt{conjecture}{theorem}
\newtheorem{conjecture}[conjecture]{Conjecture}
\aliascntresetthe{conjecture}
\theoremstyle{definition}
\newaliascnt{definition}{theorem}
\newtheorem{definition}[definition]{Definition}
\aliascntresetthe{definition}
\theoremstyle{remark}
\newaliascnt{remark}{theorem}
\newtheorem{remark}[remark]{Remark}
\aliascntresetthe{remark}
\newcommand{\LP}{\operatorname{LP}}
\newcommand{\OPT}{\operatorname{OPT}}
\newcommand{\supp}{\operatorname{supp}}
\newcommand{\rank}{\operatorname{rank}}
\newcommand{\aff}{\operatorname{aff}}
\newcommand{\conv}{\operatorname{conv}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\one}{\mathbf 1}
\newcommand{\R}{\mathbb R}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\Pcal}{\mathcal P}
\newcommand{\Zcal}{\mathcal Z}
\newcommand{\Ccal}{\mathcal C}
\newcommand{\Acal}{\mathcal A}
\newcommand{\Excl}{\mathsf E}
\setlist[enumerate]{label=(\roman*),leftmargin=2.1em,itemsep=0.2em,topsep=0.4em}
\hypersetup{pdftitle={Additive Rounding for LP-Tight Three-Item Bin Packing},
 pdfauthor={Ruixue Yuan; Da Teng; Zhenyu Sun},pdfsubject={Zero-sum patterns and additive integrality gaps},
 pdfkeywords={bin packing, configuration linear program, hypergraph matching, lattice polytope}}
\title[Additive rounding for LP-tight three-item bin packing]
{Additive Rounding for LP-Tight Three-Item Bin Packing}
\author{Ruixue Yuan}
\author{Da Teng}
\author{Zhenyu Sun}
\date{}
\subjclass[2020]{90C27, 05C65, 05C70, 52B20}
\keywords{bin packing, configuration linear programming, hypergraph matching,
zero-sum patterns, lattice polytopes}
\begin{document}
\raggedbottom
\begin{abstract}
We consider bin-packing instances with \(3m\) items of sizes in
\((1/4,1/2)\), total size \(m\), and configuration linear programming
value \(m\). Let \(d\) be the relative dimension of the polytope of
zero-sum multiplicity patterns obtained by centering sizes at \(1/3\).
We determine the maximum additive integrality gap for every \(d\le10\).
It is zero for \(d\le4\) and one for \(5\le d\le10\).
More generally, a representation of the multiplicity vector by at most
five zero-sum patterns admits an integral packing, and a representation
by at most eleven patterns requires at most one additional bin. The
integral-packing result has a structural proof; the additive-one result
combines structural restrictions with exact finite enumeration. For
arbitrary \(d\), we construct an LP-tight subinstance with at most
\(6d+3\) items and no smaller additive gap. An integer representation
preserving the signs of triple sums then yields a finite rational family attaining the
worst gap, which is computable in time \(2^{O((d+1)^2)}\). Finally,
we construct a sharp family with simplex pattern polytopes and a linearly
growing zero-sum matching deficit. Its eleven-dimensional member violates
the zero-sum remainder condition used in the ten-dimensional proof. Thus
the bound of eleven fractional patterns in that condition is sharp.
\end{abstract}
\maketitle

\section{Introduction and main results}\label{sec:introduction}

The configuration linear program is a fundamental relaxation for bin
packing and cutting stock. It represents a fractional packing as a
nonnegative combination of feasible configurations. The formulation
originates in the work of Gilmore and Gomory \cite{GilmoreGomory1961}.
Karmarkar and Karp \cite{KarmarkarKarp1982} established a
polylogarithmic additive approximation bound. Subsequent improvements by
Rothvo\ss\ \cite{Rothvoss2013} and by Hoberg and Rothvo\ss\
\cite{HobergRothvoss2017} reduced the additive bound to logarithmic
order. The integer round-up property requires
\(\OPT(I)=\lceil\LP(I)\rceil\); the modified integer round-up
inequality allows one further bin.

We study the class of instances satisfying
\begin{equation}\label{eq:class}
 |V|=3m,\qquad \frac14<s_v<\frac12\quad(v\in V),\qquad
 \sum_{v\in V}s_v=\LP(I)=m,
\end{equation}
where \(m\) is a positive integer, \(V\) is the labelled item
set, and \(s_v\) is the size of item \(v\). The relaxation
\(\LP(I)\) uses configurations that can be formed from the actual
items. We write \(\OPT(I)\) for the minimum number of bins. Every
pair fits in a bin, and no bin contains four items. Equality between the
fractional optimum and the total size forces every positively weighted
configuration in an optimum fractional solution to be a full triple.

Put \(a_v=s_v-1/3\). The full triples have centered sum zero and
admit a fractional perfect matching. If \(\nu_{\le0}(I)\) is the
maximum number of disjoint nonpositive-sum triples, then
\begin{equation}\label{eq:intro-formula}
 \OPT(I)=m+\left\lceil\frac{m-\nu_{\le0}(I)}2\right\rceil.
\end{equation}
Thus the inequality
\begin{equation}\label{eq:one}
 \OPT(I)\le m+1
\end{equation}
is equivalent to \(\nu_{\le0}(I)\ge m-2\). We write \(\nu_0(I)\)
for the maximum number of disjoint zero-sum triples. A packing in exactly
\(m\) bins consists entirely of such triples.

Group equal centered values into \(t\) classes, with distinct values
\(\beta_1,\ldots,\beta_t\) and multiplicities
\(n\in\Z_{>0}^t\). Define
\begin{equation}\label{eq:intro-polytope}
 \Zcal_I=\{p\in\Z_{\ge0}^t:\one^Tp=3,\ \beta^Tp=0,\ p\le n\},
 \qquad \Pcal_I=\conv\Zcal_I.
\end{equation}
The fractional perfect matching condition is \(n\in m\Pcal_I\).
Throughout, \(\dim\Pcal_I\) is the relative dimension of the
complete zero-sum pattern polytope. For an integer \(d\ge0\), set
\begin{equation}\label{eq:gap-function}
 \Delta_d=\sup\{\OPT(I)-\LP(I): I\text{ satisfies }
 \eqref{eq:class},\ \dim\Pcal_I\le d\}.
\end{equation}
The number of items is unrestricted in this definition.

\subsection{Exact gaps through dimension ten}

\begin{theorem}\label{thm:main}
Let \(I\) satisfy \eqref{eq:class}.
\begin{enumerate}
\item If \(n\) is a nonnegative real combination of at most five
members of \(\Zcal_I\), then \(\nu_0(I)=m\) and \(\OPT(I)=m\).
\item If \(n\) is a nonnegative real combination of at most eleven
members of \(\Zcal_I\), then
\[
 \nu_{\le0}(I)\ge m-2,\qquad \OPT(I)\le m+1.
\]
\end{enumerate}
In particular, \(\OPT(I)=m\) if \(\dim\Pcal_I\le4\), and
\(\OPT(I)\le m+1\) if \(\dim\Pcal_I\le10\).
\end{theorem}

\begin{corollary}\label{cor:exact-gaps}
The exact maximum gaps through dimension ten are
\begin{equation}\label{eq:exact-gaps}
 \Delta_d=
 \begin{cases}
  0,&0\le d\le4,\\
  1,&5\le d\le10.
 \end{cases}
\end{equation}
Thus dimension five is the smallest complete pattern dimension at which
a positive additive gap occurs in \eqref{eq:class}.
\end{corollary}

The two assertions of \cref{thm:main} use a common integer
remainder. An independent pattern representation permits removal of the
integer parts of its coefficients. The fractional parts and their
complements then determine two positive integer multiplicity vectors on
the same support. Their coordinate sums bound the remainder size.
Distinct zero-sum patterns overlap in at most one item, and patterns with
a repeated value form disjoint directed paths on the value classes.
For five patterns these facts give a complete structural argument. For
eleven patterns they reduce the additive-one bound to seven finite
matrix statements. We prove the largest-remainder statement directly
and verify all seven by exact enumeration.

The dimension bounds also give statements in terms of the number of item
types. An instance in \eqref{eq:class} with at most six distinct sizes
has an integral packing in \(m\) bins; one with at most twelve
distinct sizes requires at most \(m+1\) bins. Independently of the number of patterns,
the additive-one bound holds for \(m\le7\), by F\"uredi's
fractional matching theorem \cite{Furedi1981} and the rigidity of
zero-sum Fano planes.

\subsection{Finite extremal instances in arbitrary dimension}

\begin{theorem}\label{thm:finite-intro}
Let \(I\) satisfy \eqref{eq:class}, and put \(d=\dim\Pcal_I\).
There is a subinstance \(I'\) satisfying the same conditions, with
\(3m'\) items, such that
\begin{equation}\label{eq:finite-intro}
 m'\le2d+1,\qquad \dim\Pcal_{I'}\le d,\qquad
 \OPT(I)-m\le\OPT(I')-m'.
\end{equation}
For every fixed \(d\), the supremum \(\Delta_d\) is attained by
a rational instance with at most \(6d+3\) items and binary encoding
length \(O((d+1)^2)\). It can be computed by a deterministic algorithm
in time \(2^{O((d+1)^2)}\).
\end{theorem}

The subinstance retains the original sizes and enough copies of every
selected value to keep all selected patterns available. Its fractional
representation therefore remains a fractional perfect matching on actual
items. Replacing the centered values by bounded integers while preserving
all triple signs gives a finite rational family depending only on \(d\).
The maximum gap over that family equals the maximum over the entire
class in \eqref{eq:gap-function}.

The quantifiers in this result concern all instances of a fixed pattern
dimension. Goemans and Rothvo\ss\ \cite{GoemansRothvoss2020} give a
polynomial-time algorithm for a specified bin-packing instance with a fixed
number of item types and binary-encoded data. Here the extremal instance
itself is allowed to vary, and its size and encoding length are bounded
solely in terms of the pattern dimension.

\subsection{Sharp families and the twelve-pattern obstruction}

\begin{theorem}\label{thm:family-intro}
For every integer \(B\ge1\), there is a rational instance \(I_B\)
satisfying \eqref{eq:class} for which
\begin{align*}
 |I_B|&=18B,& \LP(I_B)&=6B,& \OPT(I_B)&=6B+1,\\
 \dim\Pcal_{I_B}&=6B-1,& \nu_0(I_B)&=4B,&
 \nu_{\le0}(I_B)&=6B-1.
\end{align*}
The complete pattern polytope is a simplex. The integer remainder obtained
from its unique fractional representation has \(9B\) items and maximum
zero-sum matching size \(B\).
\end{theorem}

For \(B=1\), this theorem supplies the dimension-five example in
\cref{cor:exact-gaps}. For \(B=2\), it gives an instance with
complete pattern dimension eleven and twelve independent patterns. Its
eighteen-item remainder has only two disjoint zero-sum triples. The
condition used in the ten-dimensional proof would require three, followed
by one nonpositive-sum triple from the remaining nine items. That condition
holds for all basic remainders with at most eleven columns and at least
nine items, and it fails
at twelve columns even when those columns are the complete zero-sum
pattern set. The family itself continues to satisfy the additive-one
bound. Moreover, any matching attaining \(\nu_{\le0}\ge m-2\)
in \(I_B\) uses at least \(2B-2\) strictly negative triples.

Rietz, Scheithauer, and Terno \cite{RietzScheithauerTerno2002}
constructed families failing the integer round-up property. Caprara et al.\
\cite{Caprara2015} obtained small numerical examples from the Petersen
graph. The family above specifies the complete pattern polytope and both
matching numbers simultaneously. Eisenbrand, P\'alv\"olgyi, and
Rothvo\ss\ \cite{EisenbrandPalvolgyiRothvoss2013} relate three-item
bin packing to permutation discrepancy and prove restrictions on rounding
methods. Our obstruction concerns the explicit zero-sum containment
condition for the integer remainder.

\Cref{sec:formulation} proves the matching and pattern formulations.
\Cref{sec:remainders} develops the integer remainder and its structural
properties. \Cref{sec:integral,sec:ten} prove the two assertions of
\cref{thm:main}. \Cref{sec:small} treats the bound from the number
of items. \Cref{sec:finite} proves the finite extremal reduction, and
\cref{sec:examples} constructs the sharp family and the twelve-pattern
obstruction. The finite enumeration is specified in
\cref{app:enumeration}.

\section{Zero-sum triples and the configuration relaxation}\label{sec:formulation}

\subsection{Configuration linear programming and LP tightness}

For a positive integer \(t\), write \([t]=\{1,\ldots,t\}\).
Vector inequalities are coordinatewise, \(e_u\) is a standard unit
vector, and \(\supp x=\{u:x_u\ne0\}\). A configuration of a labelled
instance \(I=(V,s)\) is a subset \(C\subseteq V\) with
\(\sum_{v\in C}s_v\le1\). Write \(\Ccal(I)\) for the family of
configurations. The configuration linear program is
\begin{equation}\label{eq:lp}
\begin{aligned}
 \LP(I)=\min\quad&\sum_{C\in\Ccal(I)}x_C\\
 \text{subject to}\quad&\sum_{C\ni v}x_C\ge1 &&(v\in V),\\
 &x_C\ge0 &&(C\in\Ccal(I)).
\end{aligned}
\end{equation}
A packing is a partition of \(V\) into configurations. Deleting unused
items from configurations shows that the corresponding integer covering
problem has the same optimum \(\OPT(I)\).

For a real assignment \(a:V\to\R\), put
\(a(U)=\sum_{v\in U}a_v\) and define the three-uniform hypergraphs
\[
 H_0(a)=\{e\in\tbinom V3:a(e)=0\},\qquad
 H_{\le0}(a)=\{e\in\tbinom V3:a(e)\le0\}.
\]
A matching is a family of disjoint edges; its maximum size is denoted by
\(\nu\). A fractional matching assigns nonnegative weights to the edges
so that the incident weights sum to at most one at each vertex. It is
perfect when every such sum equals one. Its maximum total edge weight is
\(\nu^*\). We use \(\nu_0(a)=\nu(H_0(a))\) and
\(\nu_{\le0}(a)=\nu(H_{\le0}(a))\), or the argument \(I\) when
\(a_v=s_v-1/3\).

\begin{lemma}\label{lem:tight}
Suppose \(|V|=3m\), \(1/4<s_v<1/2\), and \(\sum_v s_v=m\).
Then \(\LP(I)=m\) if and only if \(H_0(a)\) has a fractional
perfect matching, where \(a_v=s_v-1/3\). Every optimum solution of
\eqref{eq:lp} of value \(m\) has tight covering constraints and is
supported on triples of total size one.
\end{lemma}
\begin{proof}
For every feasible \(x\),
\[
 m=\sum_v s_v
 \le\sum_v s_v\sum_{C\ni v}x_C
 =\sum_Cx_C\sum_{v\in C}s_v
 \le\sum_Cx_C.
\]
At objective value \(m\), equality holds throughout. Positivity of
every \(s_v\) makes each covering constraint tight. Every configuration
of positive weight has total size one. Such a configuration has exactly
three items, since pairs have total size less than one and four items have
total size greater than one. Its centered sum is zero.
Conversely, the vertex equations of a fractional perfect matching give
\(3\sum_e x_e=|V|=3m\). Its weights are feasible in \eqref{eq:lp}
and attain the volume lower bound.
\end{proof}

\subsection{The integer optimum}

\begin{proposition}\label{prop:exact}
Under the size and total-volume assumptions of \cref{lem:tight},
\begin{equation}\label{eq:exact}
 \OPT(I)=m+\left\lceil\frac{m-\nu_{\le0}(I)}2\right\rceil.
\end{equation}
Thus \(\OPT(I)\le m+K\) is equivalent to
\(\nu_{\le0}(I)\ge m-2K\) for every integer \(K\ge0\).
\end{proposition}
\begin{proof}
Let \(q=\nu_{\le0}(I)\). A matching of size \(q\), followed by
pairing the remaining items, uses
\[
 q+\left\lceil\frac{3m-3q}{2}\right\rceil
 =m+\left\lceil\frac{m-q}{2}\right\rceil
\]
bins. Conversely, a packing with \(T\) triples has \(T\le q\).
Its other \(3m-3T\) items require at least
\(\lceil(3m-3T)/2\rceil\) bins. The resulting bound
\(m+\lceil(m-T)/2\rceil\) is at least the right-hand side of
\eqref{eq:exact}. The final equivalence follows by taking ceilings of
integers divided by two.
\end{proof}

\begin{lemma}\label{lem:average}
If \(|U|\ge3\) and \(a(U)=0\), then \(U\) contains a triple
of nonpositive sum.
\end{lemma}
\begin{proof}
Each vertex belongs to \(\binom{|U|-1}{2}\) triples, so
\[
 \sum_{T\in\binom U3}a(T)=\binom{|U|-1}{2}a(U)=0.
\]
At least one summand is nonpositive.
\end{proof}

Multiplying a finite real assignment by a sufficiently small positive
constant places all its values in \((-1/12,1/6)\) without changing
\(H_0\) or \(H_{\le0}\). Adding \(1/3\) then gives legitimate
item sizes. Hence all arguments about centered assignments below apply to
the bin-packing class \eqref{eq:class}.

\subsection{Multiplicity patterns and their polytope}

Let \(\beta=(\beta_1,\ldots,\beta_t)^T\) list the distinct centered
values, and let \(n_u\) be their multiplicities. A pattern is a
nonnegative integer vector with coordinate sum three. It represents an
actual triple precisely when it is bounded by \(n\). We use
\(\Zcal_I\) and \(\Pcal_I\) from \eqref{eq:intro-polytope}.

\begin{lemma}\label{lem:compression}
The hypergraph \(H_0(a)\) has a fractional perfect matching if and only
if
\begin{equation}\label{eq:representation}
 n=\sum_{p\in\Zcal_I}y_pp,\qquad y_p\ge0.
\end{equation}
Every such representation has \(\sum_p y_p=m\). Equivalently,
\(n\in m\Pcal_I\).
\end{lemma}
\begin{proof}
Aggregate the weights of a labelled fractional perfect matching by their
patterns. This gives \eqref{eq:representation}. Conversely, pattern
\(p\le n\) has
\(N(p)=\prod_u\binom{n_u}{p_u}>0\) labelled realizations.
Distribute its weight \(y_p\) uniformly among them. A fixed item of
class \(u\) occurs in the proportion \(p_u/n_u\) of these
realizations, including proportion zero if \(p_u=0\). Its resulting
degree is \(\sum_p y_pp_u/n_u=1\). Summing coordinates in
\eqref{eq:representation} gives \(3m=3\sum_p y_p\).
\end{proof}

For an integer multiplicity vector \(b\ge0\), let
\[
 \mathcal Q(b,\beta)=\{q\in\Z_{\ge0}^t:
 \one^Tq=3,\ \beta^Tq\le0,\ q\le b\}.
\]
Then
\begin{equation}\label{eq:pattern-packing}
 \nu_{\le0}(b,\beta)=
 \max\left\{\sum_qz_q:\sum_qz_qq\le b,\quad
 z_q\in\Z_{\ge0},\quad q\in\mathcal Q(b,\beta)\right\}.
\end{equation}
Indeed, a labelled matching supplies the counts \(z_q\). Conversely,
the coordinate inequalities allow distinct labels to be assigned to all
positions of each type. This observation will also be used when \(b\)
is an integer remainder.

\section{Integer remainders of fractional representations}\label{sec:remainders}

\subsection{Independent patterns and complementary multiplicities}

\begin{lemma}\label{lem:sparse}
If \(n\in m\Pcal_I\) and \(d=\dim\Pcal_I\), then
\[
 n=\sum_{j=1}^{\ell}\alpha_jp_j,\qquad
 \alpha_j>0,\quad \sum_j\alpha_j=m,\quad \ell\le d+1,
\]
for affinely independent \(p_j\in\Zcal_I\). These columns are
also linearly independent.
\end{lemma}
\begin{proof}
Choose a convex representation of \(n/m\) with the fewest positive
coefficients. An affine dependence among its patterns would give real
numbers \(z_j\), not all zero, with \(\sum_jz_jp_j=0\) and
\(\sum_jz_j=0\). Subtracting a suitable positive multiple of \(z\)
from the coefficient vector preserves nonnegativity and makes at least one
coefficient zero. This contradicts minimality. An affinely independent
set in a \(d\)-dimensional affine space has at most \(d+1\) members.
Finally, every linear dependence among these patterns has coefficient
sum zero, since each column has coordinate sum three. It is therefore
an affine dependence.
\end{proof}

Take such a representation and put \(b_j=\lfloor\alpha_j\rfloor\).
The inequality \(Pb\le n\) allows \(b_j\) copies of each
pattern to be assigned disjoint actual items. Remove them. Discard the
columns with integral coefficients, and write the remaining system as
\begin{equation}\label{eq:remainder}
 P=(p_1\ \cdots\ p_k),\qquad r=P\lambda,\qquad
 0<\lambda_j<1,\qquad h=\one^T\lambda\in\Z.
\end{equation}
Thus \(3h\) items remain, and \(m-h\) zero-sum triples have
already been packed. The case \(k=0\) is an integral packing.
Restrict all vectors to the rows used by \(P\), and define
\begin{equation}\label{eq:complement}
 \mu=\one-\lambda,\qquad \kappa=P\mu=P\one-r.
\end{equation}
We call \(\kappa\) the complementary multiplicity vector.

\begin{lemma}\label{lem:window}
For a nonempty remainder whose centered values are not all zero,
\begin{align}
 &r,\kappa\in\Z_{>0}^t,\quad \rank P=k,\quad
 \beta^TP=0,\quad \beta^Tr=\beta^T\kappa=0,\label{eq:identities}\\
 &\one^Tr=3h,\quad \one^T\kappa=3(k-h),\quad
 k+1\le t\le\min\{3h,3(k-h)\},\quad 3h\le2k-1.
 \label{eq:window}
\end{align}
\end{lemma}
\begin{proof}
Both vectors are integer because \(r=n-Pb\) and
\(\kappa=P\one-r\). Each retained row contains a positive entry,
so \(P\lambda\) and \(P\mu\) are strictly positive there.
Deleting unused rows does not alter column rank. All remaining identities
follow from the column sums and the zero-sum equations.

The nonzero vector \(\beta\) belongs to \(\ker P^T\), giving
\(t\ge k+1\). Positive integrality bounds \(t\) by each of
\(\one^Tr\) and \(\one^T\kappa\). In particular,
\(k+1\le3(k-h)\), which is equivalent to \(3h\le2k-1\).
\end{proof}

The all-zero remainder can be partitioned into zero-sum triples directly.
For a general remainder, an integer vector \(z\ge0\) specifies
available pattern copies exactly when \(Pz\le r\). In particular,
if \(J\subseteq\{1,\ldots,k\}\) satisfies
\begin{equation}\label{eq:containment}
 |J|=h-3,\qquad \sum_{j\in J}p_j\le r,
\end{equation}
then these patterns give \(h-3\) disjoint zero-sum triples. The
remaining nine items have total centered value zero, so
\cref{lem:average} gives one further nonpositive-sum triple. This yields
\(h-2\) triples in the remainder and \(m-2\) in the original
instance. Repeated entries in a pattern make the coordinate inequalities
in \eqref{eq:containment} essential.

\subsection{Intersections and repeated values}

\begin{lemma}\label{lem:overlap}
Distinct zero-sum patterns on distinct value classes satisfy
\begin{equation}\label{eq:overlap}
 \sum_u\min\{p_{ui},p_{uj}\}\le1\qquad(i\ne j).
\end{equation}
\end{lemma}
\begin{proof}
If the sum were at least two, choose an integer vector \(q\) of
coordinate sum two with \(q\le p_i,p_j\). Write
\(p_i-q=e_u\) and \(p_j-q=e_v\). Their zero-sum equations give
\(\beta_u=\beta_v\), hence \(u=v\) and \(p_i=p_j\).
\end{proof}

In particular, two distinct columns can be positive together in at most one
row. At most one entry equal to two can occur in a given row. A row
containing an entry three has no entry two. A pure pattern \(3e_u\)
requires \(\beta_u=0\), so there is at most one pure pattern.

For each pattern \(2e_u+e_v\), with \(u\ne v\), draw the
directed edge \(u\to v\) on the value classes.
\begin{lemma}\label{lem:paths}
These directed edges form vertex-disjoint directed paths. They do not
meet the row of a pure pattern.
\end{lemma}
\begin{proof}
The equation for such a pattern is \(\beta_v=-2\beta_u\).
Distinct values make both the successor and the predecessor of any vertex
unique. A directed cycle of length \(j\) would give
\(\beta_u=(-2)^j\beta_u\); every value on it would be zero,
contrary to distinctness. If an edge met the zero-value row, its other
endpoint would also have value zero. Thus the components containing edges
are directed paths disjoint from the zero-value row.
\end{proof}

\begin{lemma}\label{lem:available}
Every nonempty remainder in \eqref{eq:remainder}, with distinct
centered values, contains a selected pattern using three distinct value
classes. In particular, this pattern is bounded by \(r\).
\end{lemma}
\begin{proof}
Suppose every selected pattern has a repeated value or is pure. If a
repeated-value pattern occurs, choose a terminal vertex \(v\) of a
path in \cref{lem:paths}. Its row appears only as the single entry
of the last edge, say column \(j\). Thus
\(r_v=\lambda_j\in(0,1)\), contrary to integrality. If no
repeated-value pattern occurs, there is only the pure zero pattern. Its
single coefficient cannot have an integer sum while lying in \((0,1)\).
Hence a column with three distinct value classes occurs. Each of its
entries is at most one, so positive integrality of \(r\) makes it
available.
\end{proof}

\begin{lemma}\label{lem:small-remainder}
If the remainder in \eqref{eq:remainder} has \(h\le4\), it
contains at least \(\max\{0,h-2\}\) disjoint nonpositive-sum
triples. If \(h\le2\), all its items can be partitioned into
zero-sum triples.
\end{lemma}
\begin{proof}
For \(h=1\), the three remaining items already form a zero-sum
triple. For \(h=2\), take the available zero-sum triple from
\cref{lem:available}; its three-item complement also has sum zero.
For \(h=3\), apply \cref{lem:average}. For \(h=4\), take
one available zero-sum triple and apply \cref{lem:average} to the
other nine items. The empty remainder needs no further packing.
\end{proof}

\section{Integral packings through dimension four}\label{sec:integral}

The support bounds reduce the integral-packing problem for five patterns
to a six-value configuration. The next two lemmas settle that configuration
using only its zero-sum equations.

\begin{lemma}\label{lem:six-values}
On six distinct real values of total sum zero, the triples using three
distinct values and having sum zero form either an empty set or a single
pair of complementary triples.
\end{lemma}
\begin{proof}
The complement of any such triple is another such triple. By
\cref{lem:overlap}, two distinct triples intersect in at most one
value. If a further triple met one member of a complementary pair in
exactly one value, it would meet the other member in exactly two, again
contradicting \cref{lem:overlap}. Thus there is no further triple.
\end{proof}

\begin{lemma}\label{lem:five-unit}
Let \(\beta\in\R^6\) have distinct coordinates and
\(\one^T\beta=0\). There is no matrix
\(P\in\Z_{\ge0}^{6\times5}\) of rank five, with column sums
three and \(\beta^TP=0\), such that
\begin{equation}\label{eq:five-unit}
 P\theta=\one_6,\qquad 0<\theta_j<1\quad(1\le j\le5).
\end{equation}
\end{lemma}
\begin{proof}
Summing rows in \eqref{eq:five-unit} gives \(\one^T\theta=2\).
By \cref{lem:available}, at least one selected column uses three
distinct values. By \cref{lem:six-values}, at most two such columns
exist. If both were selected, their sum would be \(\one_6\).
The rank assumption would then make the unique solution of
\eqref{eq:five-unit} the vector having coefficients one on those two
columns and zero on the others. Thus exactly one selected column uses
three distinct values. Denote its triple by \(S\), and its
coefficient by \(\sigma\).

Let \(\eta\in\{0,1\}\) indicate whether a pure zero column is
selected. The other \(4-\eta\) columns are repeated-value
patterns. Their directed graph is a union of paths by
\cref{lem:paths}. Every nonzero value lies on one of these paths.
Indeed, a nonzero row outside the paths would appear only in \(S\),
forcing \(\sigma=1\). A zero row, if present, cannot lie on a
repeated-value path. It must have a pure column, since otherwise the same
argument would force \(\sigma=1\). Consequently the paths cover
exactly \(6-\eta\) vertices and have \(4-\eta\) edges, so
there are exactly two paths. Each terminal vertex belongs to \(S\),
because otherwise its row equation would force the coefficient of its
last edge to be one.

Along a path starting at a value \(b\), the values are
\(b,-2b,4b,\ldots\). The starts of both paths are nonzero. We
now consider their possible lengths.

Suppose \(\eta=0\). The lengths are either \((2,2)\) or
\((1,3)\). For lengths \((2,2)\), the values are
\[
 a,-2a,4a,\qquad b,-2b,4b.
\]
Their total sum gives \(b=-a\). The two terminal values in
\(S\) therefore sum to zero. Its third value would have to be
zero, although all six path values are nonzero.

For lengths \((1,3)\), write the values as
\[
 a,-2a,\qquad b,-2b,4b,-8b.
\]
The total sum gives \(a=-5b\). The terminal values \(-2a\)
and \(-8b\) sum to \(2b\), so
\(S=\{-2a,-8b,-2b\}\). Let \(u\) be the coefficient of
the short-path column, and let \(v,w,z\) be the successive
coefficients on the long path. The rows for \(a,-2a,b,-2b\)
give
\[
 2u=1,\qquad u+\sigma=1,\qquad
 2v=1,\qquad v+2w+\sigma=1.
\]
Hence \(u=v=\sigma=1/2\) and \(w=0\), contrary to
\eqref{eq:five-unit}.

Finally, suppose \(\eta=1\). The path lengths are \((1,2)\),
and the six values are
\[
 0,\qquad a,-2a,\qquad b,-2b,4b.
\]
Their total sum gives \(a=3b\). The terminal values sum to
\(-2b\), so the third value of \(S\) must be \(2b\).
The remaining values are \(0,3b,b,-2b\), none of which equals
\(2b\), since \(b\ne0\). This exhausts the possibilities.
\end{proof}

\begin{proof}[Proof of the first assertion of \cref{thm:main}]
Choose an independent representation supported on at most five of the
given patterns, and form its integer remainder. An all-zero remainder
can be partitioned directly. Otherwise \eqref{eq:window} gives
\(3h\le2k-1\le9\), so \(h\le3\). The cases \(h\le2\)
have integral packings by \cref{lem:small-remainder}.

If \(h=3\), the same bounds force \(k=5\) and \(t=6\).
The positive integer vector \(\kappa\) has coordinate sum
\(3(k-h)=6\), hence \(\kappa=\one_6\). It follows that
\(\one^T\beta=0\) and
\(P\mu=\one_6\) with \(0<\mu<1\), contrary to
\cref{lem:five-unit}. Therefore \(h=3\) cannot occur. The
integral remainder packing, together with the triples removed initially,
uses exactly \(m\) zero-sum triples. The volume lower bound gives
\(\OPT(I)=m\). If \(\dim\Pcal_I\le4\),
\cref{lem:sparse} supplies the required five-pattern representation.
\end{proof}

\section{The additive-one theorem through dimension ten}\label{sec:ten}

\subsection{A finite family of matrix statements}

For integers \(5\le h<k\), let \(\Acal_{k,h}\) consist of the
pairs \((P,\kappa)\) with the following properties. The matrix
\(P\in\Z_{\ge0}^{t\times k}\) has column sums three and rank
\(k\). The vectors \(\kappa\) and \(r=P\one-\kappa\) are
strictly positive and integral. There is a solution
\[
 P\mu=\kappa,\qquad 0<\mu_j<1,\qquad
 \one^T\mu=k-h.
\]
The space \(\ker P^T\) contains a vector with distinct coordinates.
Finally, every \((h-3)\)-subset \(J\) of columns satisfies
\(\sum_{j\in J}p_j\not\le r\). Write \(\Excl(k,h)\) for
the assertion \(\Acal_{k,h}=\varnothing\).

\begin{proposition}\label{prop:finite-reduction}
For representations supported on at most eleven patterns, it suffices to
prove \(\Excl(k,h)\) for
\begin{equation}\label{eq:seven}
 (k,h)\in\{(8,5),(9,5),(10,5),(10,6),(11,5),(11,6),(11,7)\}.
\end{equation}
\end{proposition}
\begin{proof}
Choose an independent positive representation using a subset of the given
patterns, and form \eqref{eq:remainder}. The cases \(h\le4\) are
settled by \cref{lem:small-remainder}. If \(h\ge5\),
\eqref{eq:window} and \(k\le11\) give exactly
\eqref{eq:seven}. The corresponding exclusion supplies
\eqref{eq:containment}, which gives \(h-2\) nonpositive-sum
triples as above.
\end{proof}

\subsection{Rows supported on one column}

Call a row \emph{private} if it is positive in exactly one column. Its
positive entry and its two multiplicities obey
\begin{equation}\label{eq:private}
 (\kappa_u,r_u;p_{uj})\in
 \{(1,1;2),(1,2;3),(2,1;3)\}.
\end{equation}
Indeed, \(p_{uj}\mu_j=\kappa_u\) and
\(p_{uj}(1-\mu_j)=r_u\) are positive integers whose sum is at
most three. Let \(a\) be the number of private rows of the first
kind, and let \(p_1,p_2\) count the other two kinds. Then
\(p_1+p_2\le1\). These \(c=a+p_1+p_2\) rows lie in
\(c\) distinct columns, each unavailable in the remainder.

A private double column has one additional entry, in a nonprivate row.
We call it the attachment row of that column. By
\cref{lem:paths}, these \(a\) attachment rows are distinct.
Consequently,
\begin{equation}\label{eq:private-count}
 c+a\le t.
\end{equation}
Only subsets of the other \(k-c\) columns need to be considered in
the noncontainment condition defining \(\Acal_{k,h}\).

\subsection{An extremal inequality for unit complementary multiplicities}

For \(q\ge1\), set
\begin{equation}\label{eq:turan-number}
 \tau_q(N)=\sum_{i=1}^q\binom{N_i}{2},\qquad
 \sum_iN_i=N,\quad |N_i-N_j|\le1.
\end{equation}
The complementary form of Tur\'an's theorem \cite{Turan1941} states
that a graph on
\(N\) vertices with independence number at most \(q\) has at
least \(\tau_q(N)\) edges. Equality holds precisely for a union
of \(q\) complete graphs whose orders differ by at most one; empty
parts are permitted. We use both the inequality and its equality case.

\begin{lemma}\label{lem:unit-bound}
Suppose \((P,\kappa)\in\Acal_{k,h}\) and
\(\kappa=\one\). Let \(a\) count the private double columns,
let \(p\in\{0,1\}\) count the private pure column, and put
\(c=a+p\). Then
\begin{equation}\label{eq:unit-bound}
 t\ge 2c-p+\tau_{h-4}(k-c).
\end{equation}
\end{lemma}
\begin{proof}
Since \(r_u=\sum_jp_{uj}-1\), a row violates
\(\sum_{j\in J}p_j\le r\) exactly when its entire support is
contained in \(J\). Restrict attention to subsets of the \(k-c\)
nonprivate columns. The private rows and the \(a\) attachment rows
cannot give such a violation. Any remaining row whose support lies in these
columns has support size at least two. Choose a pair of columns in each of
these supports and form a simple graph on the \(k-c\) columns.

An independent set of size \(h-3\) contains no chosen pair and hence
no complete row support. It would therefore satisfy all capacity
inequalities, a contradiction. The graph has independence number at most
\(h-4\) and at most \(t-c-a\) edges. The extremal bound gives
\(t\ge c+a+\tau_{h-4}(k-c)\), as claimed.
\end{proof}

For example, \(k=10,h=6,t=12\) forces
\(\kappa=\one\). The minimum of the right-hand side of
\eqref{eq:unit-bound}, over the allowed integers \(c,p\), is
thirteen. Thus this case is excluded directly.

\subsection{Eleven columns with remainder size twenty-one}

\begin{proposition}\label{prop:eleven-seven}
The assertion \(\Excl(11,7)\) holds.
\end{proposition}
\begin{proof}
Suppose \((P,\kappa)\in\Acal_{11,7}\). The bounds
\eqref{eq:window} imply \(t=12\) and \(\kappa=\one\).
Substitution in \eqref{eq:unit-bound} leaves the four rows of
\cref{tab:extremal}. Each attains equality.

\begin{table}[ht]
\centering
\caption{The equality possibilities for \(k=11,h=7\).}
\label{tab:extremal}
\begin{tabular}{ccccc}
\toprule
\(p\)&\(a\)&\(k-c\)&Graph on nonprivate columns&Edges\\
\midrule
1&1&9&\(K_3\sqcup K_3\sqcup K_3\)&9\\
1&2&8&\(K_3\sqcup K_3\sqcup K_2\)&7\\
1&3&7&\(K_3\sqcup K_2\sqcup K_2\)&5\\
1&4&6&\(K_2\sqcup K_2\sqcup K_2\)&3\\
\bottomrule
\end{tabular}
\end{table}

For completeness, when \(p=0\) the expression
\(2c+\tau_3(11-c)\) is at least thirteen. When \(p=1\),
the inequality \(2c-1+\tau_3(11-c)\le12\) holds exactly for
\(c=2,3,4,5\), with equality in each case.

Equality in \cref{lem:unit-bound} means that all rows other than
private and attachment rows contribute distinct edges of the displayed
extremal graph. Each such row has support exactly two. To see this last
claim, suppose a row also contains a third column. Replace its chosen edge
by another pair from that support. If the third column belongs to the same
complete component, the replacement duplicates an existing edge and reduces
the number of distinct edges below the extremal value. If it belongs to
a different component, remove the original edge \(xy\) and use an
edge \(xz\) between components. Choose \(x,y\), one vertex
from the component of \(z\) other than \(z\), and one from
the third component. These form an independent set of size four. Both
possibilities contradict the construction in \cref{lem:unit-bound}.

Every private double column has coefficient \(1/2\). Its attachment
row has right-hand side one, so the other columns contribute exactly
\(1/2\) there. Hence
\begin{equation}\label{eq:half-bound}
 \mu_j\le\tfrac12
 \quad\text{for every nonprivate column meeting an attachment row.}
\end{equation}

Consider a component \(K_2\). Each of its two columns meets one
graph row and must use an attachment row to complete its column sum.
If its entry in the graph row were two, its remaining single entry would
be in an attachment row. This would give two repeated-value columns with
the same terminal row, contradicting \cref{lem:paths}. Both entries
in the graph row are therefore one. Its equation is
\(\mu_i+\mu_j=1\), so \eqref{eq:half-bound} forces both
coefficients to be \(1/2\).

In a component \(K_3\), each column meets two graph rows. Either
it has entry one in each and a third entry in an attachment row, or it has
entries two and one in the graph rows and no other entry. In the latter
case it defines a directed edge between those two graph rows. If all three
columns have this form, the degree restrictions in \cref{lem:paths}
force a directed cycle. If exactly one column has this form, the three row
equations can be written
\[
 x+y=1,\qquad x+2z=1,\qquad y+z=1.
\]
Their solution is \((x,y,z)=(1/3,2/3,1/3)\). The coefficient
\(y\) belongs to a column meeting an attachment row and contradicts
\eqref{eq:half-bound}. If exactly two columns have repeated entries,
the corresponding edges form a directed path. The equations become
\[
 a'+2b'=1,\qquad b'+2c'=1,\qquad a'+c'=1,
\]
with solution \((a',b',c')=(3/5,1/5,2/5)\). The first column
meets an attachment row, again contradicting \eqref{eq:half-bound}.
Thus every graph-row entry is one, and all three coefficients are
\(1/2\).

It follows that all ten nonpure columns have coefficient \(1/2\).
The pure column has coefficient \(1/3\). Their sum is
\(5+1/3=16/3\), whereas \(\one^T\mu=11-7=4\).
This contradiction proves the assertion.
\end{proof}

\subsection{The finite exclusions and the main theorem}

\begin{proposition}\label{prop:enumeration}
All seven assertions in \eqref{eq:seven} hold.
\end{proposition}
\begin{proof}
For each pair \((k,h)\), enumerate all lengths in
\eqref{eq:window}, all positive integer vectors \(\kappa,r\)
with the specified sums, and all nonnegative integer matrices with the
required column and row sums. The private-row description
\eqref{eq:private}, the intersection restriction
\eqref{eq:overlap}, and the directed-path restriction reduce this
finite enumeration. \Cref{app:enumeration} proves that the row and
column orderings retain a representative of every possible system and
justifies the further pruning rules.

Every matrix reaching the terminal calculation is excluded by an integer
identity proving inconsistency, deficient column rank, or a uniquely
forced coefficient outside \((0,1)\). The complete counts appear
in \cref{tab:enumeration}. The data contain the identity for each
terminal matrix. Independent integer arithmetic checks these identities;
a second enumeration of the initial row data checks the range of the
completed calculations. No terminal matrix survives.

The last row of parameter values also has the direct proof in
\cref{prop:eleven-seven}.
\end{proof}

\begin{proof}[Proof of the second assertion of \cref{thm:main}]
By \cref{prop:finite-reduction,prop:enumeration}, every remainder
arising from a representation on at most eleven patterns contains at least
\(h-2\) nonpositive-sum triples when \(h\ge2\). Together
with the \(m-h\) triples removed initially, these give at least
\(m-2\) triples. The cases \(h=0,1\) are immediate from the
already removed triples. Apply \cref{prop:exact}.

If \(\dim\Pcal_I\le10\), \cref{lem:sparse} gives a
representation with at most eleven patterns. For the assertions about item types in the introduction,
if all centered values are zero, integral packing is immediate. Otherwise
\(\one\) and \(\beta\) are independent: a nonzero constant
\(\beta\) admits no zero-sum pattern. All patterns lie in the two
independent affine hyperplanes \(\one^Tp=3\) and
\(\beta^Tp=0\). Thus \(\dim\Pcal_I\le t-2\). The two parts of the theorem
apply when \(t\le6\) and \(t\le12\), respectively.
\end{proof}

\begin{corollary}\label{cor:fractional-support}
Suppose \(n=\sum_j\alpha_jp_j\) is any representation by
available zero-sum patterns with \(\alpha_j\ge0\). If at most
eleven coefficients are nonintegral, then \(\OPT(I)\le m+1\).
\end{corollary}
\begin{proof}
Remove all integer parts. If the remaining columns are dependent, take a
vertex of the nonempty bounded polytope
\(\{x\in[0,1]^k:Px=r\}\). Its columns with coordinates
strictly between zero and one are linearly independent, since a dependence
would allow a two-sided perturbation. Remove the patterns with coordinate
one and discard the columns with coordinate zero. At most eleven
independent fractional columns remain, so the remainder proof of
\cref{thm:main} applies. Every removed pattern is available because
its total contribution is bounded by the current integer multiplicities.
\end{proof}

\section{Instances with at most twenty-one items}\label{sec:small}

The number of items gives a second route to the additive bound, independent
of the number of patterns. We use the following fractional matching theorem
of F\"uredi \cite{Furedi1981}.

\begin{theorem}[F\"uredi]\label{thm:furedi}
For every finite three-uniform hypergraph \(H\),
\[
 \nu^*(H)\le\tfrac73\nu(H).
\]
If \(H\) contains no copy of the Fano plane, then
\(\nu^*(H)\le2\nu(H)\).
\end{theorem}

Here a Fano plane consists of seven vertices and seven triples, with each
pair of vertices in exactly one triple. Its seven triples are called lines.
Containing a copy means containing its lines as edges; additional edges are
allowed.

\begin{lemma}\label{lem:fano}
If all seven lines of a Fano plane have sum zero under a real assignment,
then all seven vertex values are zero.
\end{lemma}
\begin{proof}
Let \(S\) be the sum of the seven values. Summing the line equations
counts each vertex three times, so \(3S=0\). Fix a vertex \(v\).
There are four lines not containing \(v\), and each other vertex lies
on two of them. Their equations give \(2(S-a_v)=0\). Thus
\(a_v=S=0\) for every \(v\).
\end{proof}

Let \(z\) be the number of zero-valued items and let \(H'\) be
obtained from \(H_0\) by deleting all triples made entirely of
zero-valued items. Every edge of \(H'\) contains at most one
zero-valued item, since two zero values in a zero-sum triple force the third
to be zero. By \cref{lem:fano}, \(H'\) contains no Fano plane.
If \(x\) is a fractional perfect matching of \(H_0\), its
restriction to \(H'\) covers each nonzero-valued item with total
weight one. Consequently,
\[
 3m-z
 =\sum_{e\in E(H')}x_e\,|e\setminus\{v:a_v=0\}|
 \le3\sum_{e\in E(H')}x_e.
\]
Applying \cref{thm:furedi} gives the useful estimate
\begin{equation}\label{eq:nonzero-matching}
 \nu(H')\ge\left\lceil\frac{3m-z}{6}\right\rceil.
\end{equation}

\begin{theorem}\label{thm:small}
Every instance satisfying \eqref{eq:class} with \(m\le7\)
has \(\nu_{\le0}(I)\ge m-2\), and hence \(\OPT(I)\le m+1\).
\end{theorem}
\begin{proof}
A fractional perfect matching of \(H_0\) has weight \(m\).
For \(m\le5\), the first bound in \cref{thm:furedi} yields
\(\nu(H_0)\ge\lceil3m/7\rceil\ge m-2\).

Let \(m=6\). It suffices to find three disjoint zero-sum triples,
then use \cref{lem:average} on the other nine items; a matching
of four zero-sum triples already meets the target. If \(z\le6\),
\eqref{eq:nonzero-matching} gives three edges of \(H'\).
If \(z=7\), it gives two edges using at most two zero-valued items;
at least five zero-valued items remain, so a further all-zero triple is
available. If \(z=8\), the same two edges leave at least six
zero-valued items and can be extended by two all-zero triples. If
\(z\ge9\), three all-zero triples are available directly.
These cases prove \(\nu_{\le0}\ge4\).

Let \(m=7\). Four disjoint zero-sum triples suffice, because the
other nine items have total zero. If \(z\le6\),
\eqref{eq:nonzero-matching} gives four edges of \(H'\). For
\(z=7\), it gives three edges, which leave at least four
zero-valued items, and hence one all-zero triple. For \(8\le z\le11\),
it gives two edges; at least \(z-2\ge6\) zero-valued items remain,
so two all-zero triples can be added. Finally, \(z\ge12\) supplies
four all-zero triples directly. Thus \(\nu_{\le0}\ge5\).
\end{proof}

\section{Finite extremal instances in arbitrary pattern dimension}\label{sec:finite}

The rounding used for \cref{thm:main} minimizes the size of the
integer remainder. A different rounding preserves the availability of every
selected pattern and therefore preserves fractional perfect matchability.
The following lemma holds for zero-sum patterns of any fixed cardinality.

\subsection{Retaining all selected patterns}

\begin{lemma}\label{lem:retain}
Let \(R\ge3\), let \(\beta\in\R^t\) have distinct
coordinates, and let \(p_1,\ldots,p_k\in\Z_{\ge0}^t\)
satisfy
\[
 \one^Tp_j=R,\qquad \beta^Tp_j=0,\qquad p_j\le n.
\]
Suppose \(n\in\Z_{>0}^t\) has a representation
\[
 n=\sum_{j=1}^k\alpha_jp_j,\qquad \alpha_j>0,\qquad
 m=\sum_j\alpha_j\in\Z.
\]
Then there are integers \(q_j\ge0\) and real numbers
\(\gamma_j>0\) such that
\begin{align}
 &r=n-Pq=P\gamma\in\Z_{>0}^t,\qquad
 p_j\le r\le n\quad(1\le j\le k),\label{eq:retain}\\
 &h=\one^T\gamma=m-\one^Tq\in\Z,
 \qquad h\le(R-1)k-1.\label{eq:retain-bound}
\end{align}
The removed items can be partitioned into \(\one^Tq\) selected
zero-sum patterns.
\end{lemma}
\begin{proof}
Set
\begin{equation}\label{eq:retain-initial}
 q_j^0=\max\{0,\lfloor\alpha_j\rfloor-(R-2)\},\qquad
 \gamma_j^0=\alpha_j-q_j^0,\qquad r^0=P\gamma^0.
\end{equation}
Then \(0<\gamma_j^0<R-1\); whenever \(q_j^0>0\), also
\(\gamma_j^0\ge R-2\). The vector \(r^0=n-Pq^0\) is
positive and integral, and \(r^0\le n\). Its coefficient sum
\(h_0=m-\one^Tq^0\) is an integer less than \((R-1)k\).

Fix a coordinate \(u\). If no removed pattern uses \(u\), then
\(r_u^0=n_u\), which accommodates every selected pattern. Otherwise
choose \(i\) with \(q_i^0>0\) and \(p_{ui}>0\). Its
contribution gives \(r_u^0\ge R-2\).

Suppose first that \(\beta_u\ne0\). A zero-sum pattern uses
this value at most \(R-1\) times. Entries at most \(R-2\)
are already accommodated. If \(p_{uj}=R-1\), then \(i=j\)
gives \(r_u^0\ge(R-2)(R-1)\ge R-1\). If \(i\ne j\),
the positive contribution of column \(j\), together with the
contribution of column \(i\), gives \(r_u^0>R-2\).
Integrality again yields \(r_u^0\ge R-1\).

There is at most one zero-value coordinate \(u_0\). A zero-sum
pattern cannot use exactly \(R-1\) copies of zero, since its last
value would also be zero. Thus its entry at \(u_0\) is at most
\(R-2\), or it is the pure pattern \(Re_{u_0}\). The former
case is already covered. If the pure pattern also fits, take
\(q=q^0\) and \(\gamma=\gamma^0\).

It remains to consider \(r_{u_0}^0<R\) when a pure pattern is
selected. Since it was available in \(n\), some removed pattern
uses \(u_0\). Removing a pure pattern would leave its coefficient at least \(R-2\) and therefore at
least \(R\) zero-valued items. Hence the removed pattern is mixed.
It contributes
at least \(R-2\) to \(r_{u_0}^0\), and the pure pattern
contributes positively. Consequently, \(r_{u_0}^0=R-1\).
Undo one removal of a mixed pattern using \(u_0\). This increases
that coordinate by at least one and decreases no coordinate, so all selected
patterns become available.

To check \eqref{eq:retain-bound} after this change, let
\(\gamma_*^0\) be the coefficient of the pure pattern. The failed
capacity inequality implies
\[
 R\gamma_*^0+(R-2)\le R-1,
 \qquad \gamma_*^0\le1/R.
\]
Hence
\[
 h_0<(R-1)(k-1)+1/R,
 \qquad h_0\le(R-1)(k-1).
\]
After undoing one removal,
\[
 h=h_0+1\le(R-1)(k-1)+1\le(R-1)k-1,
\]
where the last inequality uses \(R\ge3\). Finally, \(Pq\le n\)
allows the removed pattern positions to be filled with distinct actual items
of each type.
\end{proof}

\begin{proposition}\label{prop:subinstance}
For every instance \(I\) in \eqref{eq:class}, with
\(d=\dim\Pcal_I\), there is a subinstance \(I'\) satisfying
\eqref{eq:class}, with \(3m'\) items, such that
\begin{equation}\label{eq:subinstance}
 m'\le2d+1,\qquad \dim\Pcal_{I'}\le d,\qquad
 \OPT(I)-m\le\OPT(I')-m'.
\end{equation}
\end{proposition}
\begin{proof}
Choose the representation in \cref{lem:sparse} and apply
\cref{lem:retain} with \(R=3\). The remaining multiplicities
have \(m'\le2k-1\le2d+1\). All selected patterns are available
on these multiplicities, and their positive representation gives a
fractional perfect matching by \cref{lem:compression}. Their centered
total is zero, so the total size and the configuration optimum of the
subinstance both equal \(m'\).

Every zero-sum pattern of \(I'\) is also a zero-sum pattern of
\(I\), giving the dimension inequality. The removed items occupy
exactly \(m-m'\) bins. Combining those bins with an optimum
packing of \(I'\) gives
\(\OPT(I)\le m-m'+\OPT(I')\), as required.
\end{proof}

Thus any counterexample to an additive bound in a fixed pattern dimension
has a counterexample with at most \(6d+3\) items in the same class.
The argument preserves the item sizes of the chosen subinstance.

The corresponding statement for \(R\)-item bins follows in the
same way. If an instance has \(Rm\) items with sizes in
\((1/(R+1),1/(R-1))\), total size and configuration value both
\(m\), then every bin has at most \(R\) items and every
\((R-1)\)-set fits. Writing \(\nu^{(R)}_{\le0}\) for the
maximum matching of feasible \(R\)-sets, the counting proof of
\cref{prop:exact} gives
\[
 \OPT(I)=m+\left\lceil\frac{m-\nu^{(R)}_{\le0}}{R-1}\right\rceil.
\]
Moreover, \cref{lem:retain} produces an LP-tight subinstance with
\[
 m'\le(R-1)(d+1)-1
\]
and additive gap at least that of the original instance.

\subsection{Integer values preserving all triple signs}

\begin{lemma}\label{lem:integer-values}
Let \(R\ge3\), and let \(\beta\in\R^t\) have distinct
coordinates. There is a vector \(w\in\Z^t\) with distinct
coordinates such that
\begin{equation}\label{eq:signs}
 \sgn(p^Tw)=\sgn(p^T\beta)
 \quad\text{whenever }p\in\Z_{\ge0}^t,\ \one^Tp=R,
 \qquad \|w\|_\infty\le tR^{t-1}.
\end{equation}
The order of all coordinates is preserved as well.
\end{lemma}
\begin{proof}
Consider the finitely many linear forms \(p^Tx\) with
\(\one^Tp=R\), together with \((e_u-e_v)^Tx\) for \(u<v\).
For a form that vanishes at \(\beta\), impose equality to zero.
For a positive form impose \(L(x)\ge1\), and for a negative form
impose \(-L(x)\ge1\). A sufficiently large positive multiple of
\(\beta\) satisfies this system, so its polyhedron \(S\) is
nonempty.

The forms \(Re_u^Tx\) restrict each coordinate to the sign of
\(\beta_u\), or fix it to zero. Hence
\(f(x)=\sum_u\sgn(\beta_u)x_u\) equals \(\sum_u|x_u|\)
on \(S\), and all its nonempty bounded sublevel sets in \(S\)
are compact. The minimum is attained on a compact face. An extreme point
of that face is a vertex of \(S\).

Choose \(t\) independent active equations at a vertex and write
them as \(Bx=b\). The rows of the integer matrix \(B\) have
Euclidean norm at most \(R\), and each coordinate of \(b\)
is zero or one. By Cramer's rule,
\(w=|\det B|x\) is an integer vector. Expanding the determinant
with one column replaced by \(b\) expresses each \(w_u\), up
to sign, as a sum of at most \(t\) minors of order \(t-1\).
Hadamard's determinant inequality bounds each minor by \(R^{t-1}\).
Thus \(|w_u|\le tR^{t-1}\). Positive scaling preserves all
imposed equalities and signs. The comparison forms preserve distinctness
and coordinate order.
\end{proof}

\subsection{The largest gap at a fixed dimension}

We now show that \(\Delta_d\), defined in
\eqref{eq:gap-function}, equals a maximum over an explicitly bounded
finite family.

\begin{theorem}\label{thm:finite}
The supremum \(\Delta_d\) is attained by an instance having
\begin{equation}\label{eq:finite-family}
 |I|\le6d+3,\qquad t\le3d+3,\qquad
 s_u=\frac13+\frac{w_u}{12H+1},\qquad
 |w_u|\le t3^{t-1},\quad H=\max_u|w_u|.
\end{equation}
Its binary encoding length is \(O((d+1)^2)\). The value
\(\Delta_d\) can be computed by a deterministic algorithm in
\(2^{O((d+1)^2)}\) time.
\end{theorem}
\begin{proof}
Apply \cref{prop:subinstance} to an arbitrary instance of dimension
at most \(d\). The retained representation uses at most \(d+1\)
patterns, each supported on at most three classes. These patterns cover
all positive multiplicities, so \(t\le3d+3\).

Apply \cref{lem:integer-values} with \(R=3\). All zero-sum
and nonpositive-sum patterns remain unchanged. The multiplicity vector is
a positive combination of the retained zero-sum patterns, so its total
centered value remains zero. Consequently, fractional perfect matchability,
the complete pattern dimension, and both matching numbers are preserved.
The sizes in \eqref{eq:finite-family} belong to \((1/4,1/2)\),
including the case \(H=0\). They therefore give an instance in
the same class with the same gap as the subinstance.

There are finitely many choices in \eqref{eq:finite-family}. Each
coordinate \(w_u\) uses \(O(t)\) bits, and the multiplicities,
whose total is \(O(d+1)\), use \(O((d+1)\log(d+2))\) bits.
The common denominator has \(O(t)\) bits. Thus the total encoding
length is \(O((d+1)^2)\), and the number of candidates is at most
\(2^{O((d+1)^2)}\).

Each candidate has \(O(t^3)\) triple patterns. Fractional perfect
matchability can be tested by enumerating independent subsets of at most
\(t\) zero-sum columns and solving their linear systems exactly.
The number of systems is \(2^{O((d+1)\log(d+2))}\). Rational
matrix rank gives the complete pattern dimension. On \(N=O(d+1)\)
labelled items, maximum matching can be computed by the recurrence
\[
 M(S)=\max\left\{M(S\setminus\{v\}),\
 1+M(S\setminus e): e\ni v,\ e\subseteq S,\ a(e)\le0\right\},
\]
where \(v\in S\) is fixed at each nonempty state and \(M(\varnothing)=0\).
There are \(2^N\) states and a polynomial number of transitions
per state. All arithmetic and per-candidate work fit in the asserted
running time.

Every original gap is bounded above by the gap of a candidate satisfying
the same dimension bound. Conversely, every retained candidate belongs to
the original class. Therefore the supremum in \eqref{eq:gap-function}
equals the maximum over this finite family.
\end{proof}

\Cref{prop:subinstance,thm:finite} prove
\cref{thm:finite-intro}. In particular, for every integer \(K\ge0\),
the inequality \(\OPT(I)-\LP(I)\le K\) holds for all instances
of pattern dimension at most \(d\) if and only if it holds for the
finite family in \eqref{eq:finite-family}.

\section{Sharp families and the eleven-dimensional remainder obstruction}\label{sec:examples}

\subsection{An eighteen-item instance}

Consider the distinct centered values and multiplicities
\begin{equation}\label{eq:basic-values}
 \beta=(-34,-28,-20,7,10,13,14,17,21)^T,
 \qquad n=(2,2,2,1,3,1,3,3,1)^T.
\end{equation}
Their total multiplicity is eighteen and their weighted sum is zero.
Multiplying the values by \(1/1000\) and adding \(1/3\)
gives sizes in \((1/4,1/2)\). The complete zero-sum patterns are
\begin{equation}\label{eq:basic-patterns}
\begin{array}{lll}
 p_1=(-20,10,10),&p_2=(-20,7,13),\\
 p_3=(-28,14,14),&p_4=(-28,7,21),\\
 p_5=(-34,17,17),&p_6=(-34,13,21).
\end{array}
\end{equation}
Here a triple of values denotes its multiplicity vector in the row order
of \eqref{eq:basic-values}. Each zero-sum triple has one negative
and two positive values: two negative values have sum at most \(-40\),
which the largest positive value cannot offset. The positive pairs with
sums twenty, twenty-eight, and thirty-four are exactly those listed in
\eqref{eq:basic-patterns}.

The pattern matrix is
\begin{equation}\label{eq:basic-matrix}
 A=\begin{pmatrix}
 0&0&0&0&1&1\\
 0&0&1&1&0&0\\
 1&1&0&0&0&0\\
 0&1&0&1&0&0\\
 2&0&0&0&0&0\\
 0&1&0&0&0&1\\
 0&0&2&0&0&0\\
 0&0&0&0&2&0\\
 0&0&0&1&0&1
 \end{pmatrix}.
\end{equation}
Its columns are independent. The rows for values ten, fourteen, and
seventeen first determine the coefficients of \(p_1,p_3,p_5\);
the three negative-value rows then determine the remaining coefficients.
Moreover,
\begin{equation}\label{eq:basic-coefficients}
 A\one=2\one,
 \qquad n=A\alpha,
 \qquad \alpha=(3/2,1/2,3/2,1/2,3/2,1/2)^T.
\end{equation}
Thus \(\LP=6\), and the complete pattern polytope is a
five-dimensional simplex with the displayed unique representation.

\begin{proposition}\label{prop:basic-example}
The instance \eqref{eq:basic-values} has
\[
 \nu_0=4,\qquad \nu_{\le0}=5,\qquad \OPT=7.
\]
\end{proposition}
\begin{proof}
On the positive-labelled items, draw an edge for each pair that can occur
in a zero-sum triple. This graph is the disjoint union of four triangles:
one on the three copies of ten, one on the three copies of fourteen, one
on the three copies of seventeen, and one on the values seven, thirteen,
and twenty-one. Every zero-sum matching gives a matching in this graph,
so it has at most four edges. Taking \(p_1,p_3,p_5,p_2\)
realizes four disjoint zero-sum triples.

There are five disjoint nonpositive-sum triples
\begin{equation}\label{eq:five-triples}
 (-20,10,10),\quad(-20,7,13),\quad(-28,14,14),\quad
 (-28,10,14),\quad(-34,17,17).
\end{equation}
Their sums are \(0,0,0,-4,0\). A matching of six nonpositive-sum
triples would cover all items. Since the total sum is zero, every one of its
triples would be zero-sum, contradicting \(\nu_0=4\).
The optimum follows from \cref{prop:exact}.
\end{proof}

\begin{proof}[Proof of \cref{cor:exact-gaps}]
The first assertion of \cref{thm:main} gives \(\Delta_d=0\)
for \(d\le4\). The second gives \(\Delta_d\le1\) for
\(d\le10\). The instance in \cref{prop:basic-example} has
complete pattern dimension five and additive gap one. By monotonicity of
\(\Delta_d\), it gives \(\Delta_d\ge1\) for every \(d\ge5\).
\end{proof}

This example also distinguishes two kinds of integer remainder. Removing
\(\lfloor\alpha\rfloor=(1,0,1,0,1,0)^T\) leaves
\begin{equation}\label{eq:basic-remainder}
 r=\tfrac12A\one=\one_9.
\end{equation}
Only \(p_2,p_4,p_6\) are available, and these patterns pairwise
intersect. The values ten, fourteen, and seventeen lie in no available
zero-sum triple. Thus this remainder has no zero-sum fractional perfect
matching. The retained-pattern construction of \cref{lem:retain}
keeps the capacities needed for a fractional perfect matching.

\subsection{Separating the scales}

For \(B\ge1\), take \(B\) copies of
\eqref{eq:basic-values}, and multiply the centered values of copy
\(j\) by \(C_j=100^j\), where \(0\le j<B\).
Set
\begin{equation}\label{eq:family-sizes}
 s_{j,u}=\frac13+\frac{C_j\beta_u}{1000C_{B-1}},
 \qquad n_{j,u}=n_u.
\end{equation}
These are rational sizes in \((1/4,1/2)\). Distinct copies have
distinct centered values, because their absolute-value intervals are
disjoint.

\begin{lemma}\label{lem:scales}
Every zero-sum triple in \eqref{eq:family-sizes} belongs to a
single copy.
\end{lemma}
\begin{proof}
Work with the unnormalized integer values \(C_j\beta_u\).
The basic values are nonzero integers of absolute value between seven and
thirty-four, and no pair of basic values has sum zero. Consider a triple
using more than one scale and let \(C\) be its largest scale.
If exactly one value has this scale, its absolute value is at least
\(7C\), while the other two have total absolute value at most
\(68C/100\). If two values have scale \(C\), their sum is a
nonzero integer multiple of \(C\), with absolute value at least
\(C\). The third value has absolute value at most \(34C/100\).
Neither case permits sum zero.
\end{proof}

\begin{proof}[Proof of \cref{thm:family-intro}]
By \cref{lem:scales}, the complete zero-sum pattern matrix is
\(P_B=\operatorname{diag}(A,\ldots,A)\). It has \(6B\)
independent columns, so its convex hull is a simplex of dimension
\(6B-1\). The fractional representations in
\eqref{eq:basic-coefficients} combine to give \(\LP(I_B)=6B\).
Zero-sum edges stay within copies; hence
\(\nu_0(I_B)=4B\) by \cref{prop:basic-example}.

Choose the five triples in \eqref{eq:five-triples} in every copy.
They leave the three items
\((-34C_j,17C_j,21C_j)\). For \(1\le j<B\), add the
triple
\begin{equation}\label{eq:cross-triple}
 (-34C_j,17C_j,21C_{j-1}).
\end{equation}
These triples are pairwise disjoint and avoid the five triples already
chosen in every copy. Their sums are
\(-17C_j+21C_{j-1}<0\). We obtain
\(5B+(B-1)=6B-1\) nonpositive-sum triples. A matching of
\(6B\) such triples would have to be entirely zero-sum, since it
would cover every item of a zero-total assignment. This contradicts
\(\nu_0(I_B)=4B\). Thus \(\nu_{\le0}(I_B)=6B-1\),
and \(\OPT(I_B)=6B+1\) by \cref{prop:exact}.

The unique fractional representation has coefficients \(\alpha\)
in each copy. Its integer remainder has multiplicity one in all \(9B\)
value classes. Within each copy only the three mixed patterns
\(p_2,p_4,p_6\) are available, and they pairwise intersect.
By \cref{lem:scales}, no additional zero-sum triple joins different
copies. The maximum zero-sum matching of the remainder therefore has size
exactly \(B\).
\end{proof}

\begin{corollary}\label{cor:negative-count}
In the instance \(I_B\), every matching of at least \(6B-2\)
nonpositive-sum triples contains at least \(2B-2\) triples of
strictly negative sum.
\end{corollary}
\begin{proof}
At most \(\nu_0(I_B)=4B\) of its triples can have sum zero.
\end{proof}

\subsection{The first failure of the selected-pattern condition}

\begin{proposition}\label{prop:obstruction}
For every \(B\ge2\), the assertion \(\Excl(6B,3B)\) is
false. In particular, \(\Excl(12,6)\) is false even when the
selected columns are all the vertices of the complete pattern polytope.
\end{proposition}
\begin{proof}
Use \(P_B\) and put
\[
 \mu=\tfrac12\one_{6B},\qquad \kappa=r=\one_{9B}.
\]
The column sums, rank, and positive integer conditions follow from
\cref{eq:basic-matrix,eq:basic-coefficients}. The scaled vector
\((C_j\beta_u)_{j,u}\) has distinct coordinates and lies in
\(\ker P_B^T\). Also \(\one^T\mu=3B=k-h\).
The remainder contains at most \(B\) disjoint zero-sum triples.
Since \(B<3B-3=h-3\) for \(B\ge2\), no required column
subset is accommodated. This gives a member of \(\Acal_{6B,3B}\).
\end{proof}

For \(B=2\), the original instance has thirty-six items, pattern
dimension eleven, fractional optimum twelve, and integer optimum thirteen.
Its eighteen-item remainder contains only two disjoint zero-sum triples,
whereas \eqref{eq:containment} would require three. Because the
complete zero-sum pattern polytope is already a simplex, adding further
zero-sum columns cannot change this conclusion. The strictly negative
triples in \cref{eq:five-triples,eq:cross-triple} supply the
additional packing flexibility.

\section{Further questions}\label{sec:questions}

The general additive statement for the class in \eqref{eq:class} can
be written in matching form.
\begin{conjecture}\label{conj:general}
Every real zero-total assignment on \(3m\) labelled items whose
zero-sum triple hypergraph has a fractional perfect matching satisfies
\[
 \nu_{\le0}\ge m-2.
\]
\end{conjecture}

The exact values in \cref{cor:exact-gaps} locate the first positive
additive gap at pattern dimension five. The next undetermined value is
\(\Delta_{11}\). In every fixed dimension,
\cref{thm:finite-intro} replaces the supremum over unrestricted
instances by a maximum over a bounded rational family.

For basic remainders with at least nine items and at most eleven
independent columns, the proof of \cref{thm:main} obtains the
required matching from
\eqref{eq:containment} and the nine-item averaging argument.
\Cref{prop:obstruction} gives a twelve-column remainder in which
\eqref{eq:containment} fails, although the original instance has gap
one. The family in \cref{thm:family-intro} further shows that
matchings of the required size can need a number of strictly negative
triples growing linearly with the pattern dimension. These examples
suggest studying matchings that combine zero-sum triples with exchanges
between their components.

\appendix
\section{The finite enumeration}\label[appendix]{app:enumeration}

This appendix specifies the enumeration used in
\cref{prop:enumeration}. All data and program names are relative to
the accompanying directory. The C++ source is
\texttt{code/enumerate.cpp}. The Python programs
\texttt{code/generate\_cases.py}, \texttt{code/check\_coverage.py},
and \texttt{code/check\_certificates.py} generate the initial cases
and perform independent checks. Completed calculations and their integer
identities are in \texttt{data/enumeration/}.

\subsection{Initial row data}

Fix \((k,h)\) from \eqref{eq:seven}. Enumerate each integer
\[
 k+1\le t\le\min\{3h,3(k-h)\}.
\]
Enumerate the positive integer partitions of \(3(k-h)\) and
\(3h\) into \(t\) parts, representing \(\kappa\) and
\(r\). For each pair of partitions, fix the ordering of
\(\kappa\) and enumerate every distinct alignment of the entries
of \(r\). Within rows having the same \(\kappa\) entry,
order the \(r\) entries increasingly. Thus the data record all
multisets of pairs \((\kappa_u,r_u)\) with the prescribed sums.

Next choose \(a,p_1,p_2\) in \eqref{eq:private}, subject to the
available numbers of the three row types, \(p_1+p_2\le1\), and
\eqref{eq:private-count}. Place the private double columns first and
the pure column, if any, immediately afterwards. By simultaneously
permuting private rows and their columns, their entries can be fixed to a
diagonal block of twos followed by an optional three. All remaining rows
are nonprivate. Their coordinate sums are \(\kappa_u+r_u\), and
they are generated by all distributions of this sum among the columns with
each final column sum bounded by three. Private double columns have
remaining capacity one, the pure column has capacity zero, and the other
columns have capacity three.

This describes every possible pair \((P,\kappa)\) up to row
and column permutations. The independent program
\texttt{code/check\_coverage.py} generates the same initial set by a
different recursion. It constructs the sorted sequence of pairs
\((\kappa_u,r_u)\) directly, without separate partitions or
alignments. It checks equality of the two sets of initial cases.

\subsection{Ordering rows and columns}

Let \(\mathcal J\) be the family of all \((h-3)\)-subsets of
the nonprivate columns. For a row vector \(v\) of type
\((\kappa_u,r_u)\), define
\begin{equation}\label{eq:row-cover}
 C_u(v)=\left\{J\in\mathcal J:\sum_{j\in J}v_j>r_u\right\}.
\end{equation}
The integer \(|C_u(v)|\) is unchanged by permuting nonprivate
columns. Row types are arranged in a fixed order. Among rows of the same
type, order first by decreasing \(|C_u(v)|\), and then by increasing
lexicographic order of the row vector. Order the nonprivate columns
lexicographically by their full column vectors. During construction, this
last rule is imposed only on adjacent columns whose prefixes are identical.

These row and column rules are compatible. In a given orbit under the
allowed row and column permutations, choose a row-major lexicographically
least matrix after sorting row types and their invariant counts
\(|C_u(v)|\). Its rows with the same type and count are already
lexicographically sorted. If two adjacent nonprivate columns first differ
in the wrong order, exchanging them strictly decreases the matrix at that
first difference. Reordering rows within the same type and count can only
further decrease it. This contradicts minimality. Hence every orbit has a
representative satisfying both ordering rules.

The private double columns are left in their initially fixed order. The
resulting repeated representatives do not affect coverage of the finite
set.

\subsection{Pruning partial matrices}

The partial matrix is extended one row at a time. Every proposed row is
subject to the remaining column capacities and has support of size at
least two. The following restrictions are consequences of
\cref{lem:overlap,lem:paths}.

Each pair of columns can meet in at most one row. At most one entry two
occurs in a row, and a row cannot contain both an entry two and an entry
three. At most one pure column occurs in the entire matrix. A row cannot
be the attachment row of two private double columns. As soon as a column
has total sum three, its repeated-value edge, if present, is determined.
The directed edges of all completed columns must have indegree and
outdegree at most one, contain no directed cycle, and avoid the pure
zero row. Their endpoints cannot change when further rows are added, so
these tests are valid before the matrix is complete.

The row sets \(C_u(v)\) must eventually cover \(\mathcal J\).
For each unused row, compute an upper bound on the number of sets that
one of its permitted distributions can cover. The sum of these bounds is
an upper bound on the number of currently uncovered sets that the unused
rows could cover. A branch is discarded when this sum is too small.
Counting the same set more than once only enlarges this upper bound and
therefore preserves every possible completion. Rows are otherwise
restricted solely by the column capacities and the ordering rules above.
When \(\kappa=\one\), \cref{lem:unit-bound} is also applied
before the row enumeration.

Upon reaching a terminal matrix, the program verifies all column sums and
the full cover of \(\mathcal J\). It then performs exact elimination
on \(P\mu=\kappa\). For \(k\le11\) and \(h\le7\), there are at most
\(\binom{11}{4}=330\) target subsets and at most
\(\binom{11}{2}=55\) column pairs. The implementation uses masks
of lengths 512 and 128, respectively. Matrix entries and capacities are
at most three, and the support bounds give \(t\le15\), within
the allocated limit of 21. Rational elimination uses arbitrary
precision integer numerators and denominators.

\subsection{Integer identities at terminal matrices}

Every terminal rejection is accompanied by one of the following integer
identities. These can be checked using additions and multiplications,
independently of the elimination used to find them.

An inconsistent system supplies \(y\in\Z^t\) with
\begin{equation}\label{eq:inconsistent-certificate}
 y^TP=0,\qquad y^T\kappa\ne0.
\end{equation}
A rank-deficient matrix supplies \(z\in\Z^k\setminus\{0\}\)
with \(Pz=0\). If the unique solution has a coefficient outside
\((0,1)\), the data contain integers \(D>0\), \(z\in\Z^k\)
with \(Pz=D\kappa\) and some \(z_j\notin(0,D)\), together
with an integer matrix \(B\) and a positive diagonal matrix
\(D'\) satisfying
\begin{equation}\label{eq:left-inverse}
 BP=D'.
\end{equation}
This proves full column rank and the uniqueness of \(\mu=z/D\).

The final possible restriction is that \(\ker P^T\) contain a
vector with distinct coordinates. This fails precisely when some pair of
coordinates agrees throughout the kernel. Indeed, if no such pair exists,
each equality cuts out a proper hyperplane in \(\ker P^T\), and
a finite union of proper real hyperplanes cannot cover that vector space.
A forced equality can be demonstrated by
\[
 Pz=q(e_u-e_v),\qquad z\in\Z^k,\quad q\in\Z_{>0}.
\]
The seven complete calculations require only
\eqref{eq:inconsistent-certificate}, rank deficiency, and
\eqref{eq:left-inverse}. Their totals are respectively
\(113\,139\), \(72\), and \(45\).

\begin{table}[ht]
\centering
\caption{Complete finite exclusions. The second column counts initial
row-data assignments, including the choices of private rows. The third
counts terminal matrices with an integer exclusion.}
\label{tab:enumeration}
\begin{tabular}{rrrr}
\toprule
\((k,h)\)&Initial cases&Terminal matrices&Surviving matrices\\
\midrule
\((8,5)\)&88&0&0\\
\((9,5)\)&692&0&0\\
\((10,5)\)&1,889&90&0\\
\((10,6)\)&648&0&0\\
\((11,5)\)&3,035&18,231&0\\
\((11,6)\)&3,035&93,381&0\\
\((11,7)\)&332&1,554&0\\
\midrule
Total&9,719&113,256&0\\
\bottomrule
\end{tabular}
\end{table}

\subsection{Completion and reproduction}

Each initial case is assigned an integer identifier. Its terminal matrices
carry that identifier, and the search writes a completion line for the case.
The program records a final completion line only after its entire assigned
set of cases has been exhausted. For \((11,6)\), the initial cases
are divided into four disjoint sets by their identifiers modulo four.
All other parameter pairs are calculated in a single set. The coverage
checker verifies that every initial identifier occurs in exactly one
completed calculation. The integer checker verifies each terminal identity
and compares the rejection counts with the corresponding completion record.

From the root of the accompanying directory,
\begin{verbatim}
python3 code/check_all.py
\end{verbatim}
checks the supplied integer identities, the initial-case coverage, the
exact examples, and the small remainders from \cref{sec:integral}.
The latter check independently lists the three possible nonempty
remainder windows for at most five columns and verifies zero-sum
decompositions. Its program is
\texttt{code/check\_low\_dimensions.py}. The command
\begin{verbatim}
python3 code/reproduce.py --output reproduction --workers 4
\end{verbatim}
regenerates all seven calculations and performs the independent checks.
It requires a C++17 compiler, the Boost headers, and Python 3.10 or later.
Checking the supplied data requires only Python's standard library.

The representative matrix for \(\Excl(12,6)\) in
\cref{prop:obstruction}, its distinct integer values, and its
fractional coefficients are included in \texttt{data/examples/}.
The example program checks the complete zero-sum pattern list, rank,
coefficient equations, capacity inequalities, and the displayed matchings.

\bibliographystyle{amsplain}
\bibliography{references}
\end{document}