betaFeedback

WorksMathematics

Boolean Rank Nine for Polygons with 35 to 40 Vertices

Abstract

We give a computer-assisted proof that the rectangle covering number, or Boolean rank, of every polygon slack matrix of order 35 through 40 is nine. The upper bound is due to Goucha, Gouveia, and Silva; the new contribution is the matching lower bound. A hypothetical covering by eight rectangles yields a saturated inclusion cycle between two antichains on eight coordinates. An exact maximal-chain identity bounds its length and assigns a nonnegative penalty to each inclusion edge. The equality case is excluded combinatorially, leaving at most 39 lower vertices. For orders 35 through 39, symmetry reductions and a shadow bound leave fifteen finite exclusions, each supported by a checked reverse-unit-propagation refutation. The main text presents the mathematical reductions and their dependencies; the accompanying supplement gives the complete cycle parameters, encodings, and certificate record. The previously known equality for orders 41 through 55 is cited directly.

Problem, prior results, and proof strategy

Polygon supports and rectangle coverings

The support of a polygon slack matrix has a simple cyclic form, even though its positive entries depend on the geometry. Let PP be a convex polygon with exactly nn vertices and nn irredundant facet inequalities. After cyclically indexing rows and columns, its slack matrix SPS_P has the support of the zero-one matrix MnM_n defined by

(Mn)ij=0⟺i=j or i=j+1(modn).(1)(M_n)_{ij}=0 \quad\Longleftrightarrow\quad i=j\ \text{or}\ i=j+1\pmod n. \tag*{(1)}

All other entries are one. Explicitly, the support matrix has the cyclic form

Mn=(011⋯10001⋯11100⋯11⋮⋱⋱⋱⋮⋮1⋯10011⋯1100).M_n= \begin{pmatrix} 0 & 1 & 1 & \cdots& 1 & 0\\ 0 & 0 & 1 & \cdots& 1 & 1\\ 1 & 0 & 0 & \cdots& 1 & 1\\ \vdots& \ddots& \ddots& \ddots& \vdots& \vdots\\ 1 & \cdots& 1 & 0 & 0 & 1\\ 1 & \cdots& 1 & 1 & 0 & 0 \end{pmatrix}.

A rectangle of a nonnegative matrix MM is a set I×JI\times J contained in supp⁡(M)\operatorname{supp}(M). The rectangle covering number RCB⁡(M)\operatorname{RCB}(M) is the smallest number of such rectangles whose union is supp⁡(M)\operatorname{supp}(M). It equals the Boolean rank rank⁡B(M)\operatorname{rank}_{\mathrm{B}}(M): the smallest inner dimension of a Boolean factorization of the support, with AND for multiplication and OR for addition.

For a nonnegative matrix, we use rank⁡B(M)\operatorname{rank}_{\mathrm{B}}(M) to mean the Boolean rank of its zero-one support matrix. Thus

RCB⁡(SP)=rank⁡B(SP)=RCB⁡(Mn)=rank⁡B(Mn).\operatorname{RCB}(S_P)=\operatorname{rank}_{\mathrm{B}}(S_P)=\operatorname{RCB}(M_n)=\operatorname{rank}_{\mathrm{B}}(M_n).

Published bounds and the remaining gap

Goucha, Gouveia, and Silva [1] studied polygon Boolean ranks through homogeneous factorizations and cycles in Johnson graphs. Their Section 3.2, Table 1 gives a size-nine factorization for every 35≤n≤5535\le n\le55. In the interval 35≤n≤4035\le n\le40, the asterisk in that table marks an upper bound whose optimality was not established. For 41≤n≤5541\le n\le55, the equality with nine is already established. Engel, Kalinowski, and Schymura [2] also list the bounds 8≤RCB⁡(Mn)≤98\le\operatorname{RCB}(M_n)\le9 for 35≤n≤4035\le n\le40.

Proposition 1.1 (Published upper bound). For every 35≤n≤5535\le n\le55, one has RCB⁡(Mn)≤9\operatorname{RCB}(M_n)\le9.

Proof. Goucha, Gouveia, and Silva give homogeneous Boolean factorizations of size nine throughout this interval [1]. Every homogeneous Boolean factorization is also an unrestricted Boolean factorization, so it gives a covering by at most nine rectangles.

The published size-nine witnesses and their entrywise checks are documented in the accompanying Supplementary Material, § 15.

Main result

Theorem 1.2. For every convex polygon PP with 35≤n≤4035\le n\le40 vertices,

RCB⁡(SP)=rank⁡B(SP)=9.\operatorname{RCB}(S_P)=\operatorname{rank}_{\mathrm{B}}(S_P)=9.

Corollary 1.3. For every convex polygon PP with 35≤n≤5535\le n\le55 vertices,

RCB⁡(SP)=rank⁡B(SP)=9.\operatorname{RCB}(S_P)=\operatorname{rank}_{\mathrm{B}}(S_P)=9.

Proof. Use Theorem 1.2 for 35≤n≤4035\le n\le40. For 41≤n≤5541\le n\le55, use the exact values already established in [1].

Proof strategy and dependencies

Only the lower bound for 35≤n≤4035 \le n \le40 is new here. Since the upper bound is already available, the task is to exclude a covering by at most eight rectangles. The proof has four steps:

  1. Section 2 turns such a covering into a saturated inclusion cycle on eight coordinates.

  1. Section 3 proves rank restrictions and an exact penalty budget by maximal-chain counting.

  1. Section 4 excludes equality in that budget, giving N≤39N \le39 without a computational refutation.

  1. Section 5 excludes the remaining cycles through the H, G, T, M, and F stages. Section 6 then assembles the argument.

Here nn denotes the polygon order and NN the number of lower vertices in an inclusion cycle; the normal form gives N=nN=n. The saved selection formulas allow every 35≤N≤4035 \le N \le40 simultaneously. Thus the finite exclusions use no assumption of homogeneity or monotonicity in nn.

The local stages are applied in a fixed order. H excludes homogeneous cycles. G restricts the possible rank pairs. T removes the remaining lower two-sets and, by duality, upper six-sets. M proves that mixed edges form a matching. Only then does F use this matching condition. The complete encodings and certificates are supplied in the supplement.

From rectangle coverings to inclusion cycles

Write Ωk={0,1,…,k−1}\Omega_k = \{0,1,\ldots,k-1\} and use cyclic indices in Z/nZ\mathbb{Z}/n\mathbb{Z}. The rank of a set means its cardinality. The sets below record which rectangles contain a given row or column; their ground-set coordinates label rectangles, not polygon vertices. If a covering has fewer than eight rectangles, pad it with empty rectangles. It is therefore enough to exclude coverings indexed by Ω8\Omega_8.

The maximal-rectangle normal form

Lemma 2.1 (Maximal-rectangle normal form). Suppose MnM_n has a covering by kk rectangles: I0×J0,I1×J1,…,Ik−1×Jk−1I_0 \times J_0, I_1 \times J_1,\ldots,I_{k-1} \times J_{k-1}. There is a covering by kk rectangles I0∗×J0∗,I1∗×J1∗,…,Ik−1∗×Jk−1∗I_0^* \times J_0^*, I_1^* \times J_1^*,\ldots,I_{k-1}^* \times J_{k-1}^* with row membership sets Ai={t∈Ωk:i∈It∗}A_i=\{t\in\Omega_k:i\in I_t^*\} and column membership sets Dj={t∈Ωk:j∈Jt∗}D_j=\{t\in\Omega_k:j\in J_t^*\}. Let Bj=Ωk∖DjB_j=\Omega_k\setminus D_j, then we have

Bj=Aj∪Aj+1,(2)B_j=A_j\cup A_{j+1}, \tag*{(2)}
Ai=Bi−1∩Bi,(3)A_i=B_{i-1}\cap B_i, \tag*{(3)}
Ai⊆Bj⟺i∈{j,j+1}.(4)A_i\subseteq B_j \quad\Longleftrightarrow\quad i\in\{j,j+1\}. \tag*{(4)}

Proof. For a rectangle I×JI\times J, let J∗J^* consist of every column compatible with all rows in II, and let I∗I^* consist of every row compatible with all columns in J∗J^*. Then I⊆I∗I\subseteq I^* and J⊆J∗J\subseteq J^*. A column outside J∗J^* has a zero in some row of II, hence also in a row of I∗I^*. Thus I∗×J∗I^*\times J^* is maximal on both sides. Extend every rectangle this way. No previously covered positive position is lost.

For a maximal rectangle indexed by tt, column jj belongs to the rectangle exactly when neither row jj nor row j+1j+1 belongs to it. Consequently t∈Djt\in D_j exactly when t∉Aj∪Aj+1t\notin A_j\cup A_{j+1}, proving (2). Similarly, row ii belongs to the rectangle exactly when neither column i−1i-1 nor column ii belongs to it. This gives (3).

Finally, position (i,j)(i,j) is uncovered exactly when Ai∩Dj=∅A_i\cap D_j=\varnothing, or equivalently Ai⊆BjA_i\subseteq B_j. The prescribed zero positions are precisely those in (4). □\square

Antichains and the induced cycle

Lemma 2.2. For n≥4n \ge4, sets satisfying (4) form two antichains A={Ai}\mathcal{A}=\{A_i\} and B={Bj}\mathcal{B}=\{B_j\}, each of cardinality nn. No member of A\mathcal{A} equals a member of B\mathcal{B}. The bipartite graph defined by strict inclusion A⊊BA \subsetneq B is an induced alternating cycle of length 2n2n.

Proof. If Ai⊆AhA_i \subseteq A_h, then AiA_i lies in both Bh−1B_{h-1} and BhB_h. By (4), ii belongs to both {h−1,h}\{h-1,h\} and {h,h+1}\{h,h+1\}, so i=hi=h. This proves the first antichain assertion and also distinctness of the AiA_i.

If Bj⊆BhB_j \subseteq B_h, its two lower neighbors are also lower neighbors of BhB_h. Equation (4) then implies {j,j+1}={h,h+1}\{j,j+1\}=\{h,h+1\} and hence j=hj=h. If Ai=BjA_i=B_j, the other lower neighbor of BjB_j would be contained in AiA_i, contrary to the first assertion. The last statement now follows directly from (4).

Conversely, a cyclic sequence satisfying (4), with Bj=Aj∪Aj+1B_j=A_j\cup A_{j+1}, yields a covering. Its rectangle indexed by tt is

{i:t∈Ai}×{j:t∉Aj∪Aj+1}.(5)\{i:t\in A_i\}\times\{j:t\notin A_j\cup A_{j+1}\}. \tag*{(5)}

We call a pair of antichains satisfying (2)--(4) a saturated inclusion cycle. This is a condition on the selected antichains, not a claim that the cycle is maximal among cycles in the entire Boolean lattice.

Bipartite inclusion graph and alternating cycle

Figure 1. (a) Bipartite inclusion graph \quad (b) Alternating cycle. n=6n=6.

Complement duality and homogeneity

Lemma 2.3 (Complement duality). Taking A~i=B−ic\widetilde{A}_i=B^c_{-i}, B~i=A−ic\widetilde{B}_i=A^c_{-i} preserves a saturated inclusion cycle. An inclusion edge A⊂BA\subset B has rank type (∣A∣,∣B∣)(|A|,|B|); under this transformation, rank type (a,b)(a,b) becomes (k−b,k−a)(k-b,k-a).

Proof. Taking complements and exchanging the two families preserves the antichain property. Moreover,

A~i∪A~i+1=(B−i∩B−i−1)c=A−ic=B~i,\widetilde{A}_i\cup\widetilde{A}_{i+1}=(B_{-i}\cap B_{-i-1})^c=A^c_{-i}=\widetilde{B}_i,
B~i−1∩B~i=(A1−i∪A−i)c=B−ic=A~i.\widetilde{B}_{i-1}\cap\widetilde{B}_i=(A_{1-i}\cup A_{-i})^c=B^c_{-i}=\widetilde{A}_i.

The inclusion condition is also preserved:

A~i⊆B~j⟺A−j⊆B−i⟺i∈{j,j+1}.\widetilde{A}_i\subseteq\widetilde{B}_j\quad\Longleftrightarrow\quad A_{-j}\subseteq B_{-i}\quad\Longleftrightarrow\quad i\in\{j,j+1\}.

Finally, an edge A⊂BA\subset B becomes Bc⊂AcB^c\subset A^c, whose rank type is (k−b,k−a)(k-b,k-a).

A cycle is homogeneous of type (r,r+1)(r,r+1) if every lower set has size rr and every upper set has size r+1r+1.

Maximal-chain counting and the penalty budget

The exact chain identity

A chain in 2Ωk2^{\Omega_k} is a family of subsets ordered by inclusion. It is maximal if no additional subset can be inserted while preserving this ordering. Every maximal chain has the form

C={C0,C1,…,Ck},∅=C0⊊C1⊊⋯⊊Ck=Ωk,∣Cr∣=r.C=\{C_0,C_1,\ldots,C_k\},\qquad\varnothing=C_0\subsetneq C_1\subsetneq\cdots\subsetneq C_k=\Omega_k,\qquad|C_r|=r.

Thus a maximal chain contains exactly one set of each cardinality. It is uniquely determined by a permutation (π1,…,πk)(\pi_1,\ldots,\pi_k) of Ωk\Omega_k, through

C0=∅,Cr={π1,…,πr}(1≤r≤k).C_0=\varnothing,\qquad C_r=\{\pi_1,\ldots,\pi_r\}\quad(1\le r\le k).

Choosing the permutation uniformly therefore gives a uniformly random maximal chain.

We say that CC meets a family A\mathcal A if some set on the chain belongs to A\mathcal A; equivalently,

C∩A≠∅.C\cap\mathcal A\ne\varnothing.

If A\mathcal A is an antichain, the chain can contain at most one member of A\mathcal A, since any two distinct sets on the chain are comparable by inclusion.

Lemma 3.1 (Chain identity). Let A,B\mathcal A,\mathcal B be disjoint antichains in 2Ωk2^{\Omega_k}, with every cross-comparability oriented from A\mathcal A to B\mathcal B. Let EE be the set of pairs (A,B)(A,B) with A⊊BA\subsetneq B. A uniformly random maximal chain CC satisfies

Pr⁡(C∩(A∪B)≠∅)=∑A∈A(k∣A∣)−1+∑B∈B(k∣B∣)−1−∑(A,B)∈E1(k∣B∣)(∣B∣∣A∣)≤1.(6)\Pr\bigl(C\cap(\mathcal A\cup\mathcal B)\ne\varnothing\bigr) = \sum_{A\in\mathcal A}\binom{k}{|A|}^{-1} +\sum_{B\in\mathcal B}\binom{k}{|B|}^{-1} -\sum_{(A,B)\in E}\frac{1}{\binom{k}{|B|}\binom{|B|}{|A|}} \le1. \tag*{(6)}

Proof. There are k!k! maximal chains. A set of size aa lies on a!(k−a)!a!(k-a)! of them. A nested pair of sizes a<ba<b lies on a!(b−a)!(k−b)!a!(b-a)!(k-b)! of them. A chain meets each antichain at most once. If it meets both, the two selected sets form a pair in EE. Thus inclusion–exclusion stops after the pair terms and gives the displayed identity.

In the cycles and paths considered below, every upper vertex has two lower neighbors. This excludes reverse cross-comparabilities. Indeed, if B⊆AB\subseteq A for some B∈BB\in\mathcal B and A∈AA\in\mathcal A, a lower neighbor A′A' of BB would satisfy

A′⊊B⊆A,A'\subsetneq B\subseteq A,

contradicting the antichain property of A\mathcal A.

Define, for 1≤a<b≤k−11\le a<b\le k-1,

wk(a,b)=12(ka)+12(kb)−1(kb)(ba).(7)w_k(a,b)=\frac{1}{2\binom{k}{a}}+\frac{1}{2\binom{k}{b}}-\frac{1}{\binom{k}{b}\binom{b}{a}}. \tag*{(7)}

In particular, the eight-coordinate formula is

w8(a,b)=12(8a)+12(8b)−1(8b)(ba).(8)w_8(a,b)=\frac{1}{2\binom{8}{a}}+\frac{1}{2\binom{8}{b}}-\frac{1}{\binom{8}{b}\binom{b}{a}}. \tag*{(8)}

For an inclusion cycle, every selected vertex has degree two. Therefore Lemma 3.1 becomes

∑(A,B)∈Ewk(∣A∣,∣B∣)≤1.(9)\sum_{(A,B)\in E}w_k(|A|,|B|)\le1. \tag*{(9)}

For an induced alternating path with mm lower vertices and m−1m-1 upper vertices, whose endpoints are AL,ARA_L,A_R, the corresponding inequality is

∑(A,B)∈Ewk(∣A∣,∣B∣)+12(k∣AL∣)+12(k∣AR∣)≤1.(10)\sum_{(A,B)\in E}w_k(|A|,|B|) +\frac{1}{2\binom{k}{|A_L|}} +\frac{1}{2\binom{k}{|A_R|}} \le1. \tag*{(10)}

Analytic bounds for the chain weights

Lemma 3.2 (Analytic weight minima). The chain weights satisfy

min⁡1≤a<b≤6w7(a,b)=3140,(11)\min_{1\leq a<b\leq6} w_7(a,b)=\frac{3}{140}, \tag*{(11)}
min⁡2≤a≤5, 3≤b≤6a<bw8(a,b)=180.(12)\min_{\substack{2\leq a\leq5,\ 3\leq b\leq6\\a<b}} w_8(a,b)=\frac{1}{80}. \tag*{(12)}

Equality in (11) holds only at (3, 4); equality in (12) holds only at (3, 4) and (4, 5).

Proof. For k=7k=7, all fifteen admissible pairs are listed below:

420w7(a,b)420w_7(a,b)b=2b=2b=3b=3b=4b=4b=5b=5b=6b=6
a=1a=13032333650
a=2a=2–12141836
a=3a=3––91433
a=4a=4–––1232
a=5a=5––––30

Table 1.

The smallest entry is 9, attained only at (3, 4). Thus the minimum weight is 9/420=3/1409/420=3/140.

For k=8k=8, all ten admissible pairs in the stated range are:

1680w8(a,b)1680w_8(a,b)b=3b=3b=4b=4b=5b=5b=6b=6
a=2a=235384256
a=3a=3–212742
a=4a=4––2138
a=5a=5–––35

Table 2.

The smallest entry is 21, attained only at (3, 4) and (4, 5). Thus the minimum weight is 21/1680=1/8021/1680=1/80.

The seven-coordinate path bound and rank restrictions

Lemma 3.3. An induced alternating inclusion path on a seven-element ground set, with two antichains and both endpoints in the lower antichain, has at most 23 lower vertices.

Proof. It suffices to rule out m≥24m\geq24. In that case neither antichain contains the empty set or the full ground set: these would violate either the antichain property or the degree bound of two. There are no reverse cross-comparabilities, by the same antichain argument as above, since each upper vertex has two lower neighbors. Thus the relevant ranks satisfy 1≤a<b≤61\leq a<b\leq6.

Lemma 3.2 gives w7(a,b)≥3/140w_7(a,b)\geq3/140, while binomial unimodality gives (7a)≤35\binom{7}{a}\leq35. There are 2(m−1)2(m-1) edges, so (10) implies

1≥2(m−1)3140+135=3m−170.1\geq2(m-1)\frac{3}{140}+\frac{1}{35}=\frac{3m-1}{70}.

Hence $m\leq 23.

Proposition 3.4. Every saturated inclusion cycle with N≥25N\geq25 lower vertices in 2Ω82^{\Omega_8} satisfies

2≤∣A∣≤5(A∈A),3≤∣B∣≤6(B∈B).(13)2\leq|A|\leq5\quad(A\in\mathcal{A}),\qquad3\leq|B|\leq6\quad(B\in\mathcal{B}). \tag*{(13)}

Proof. We first show that ∣A∣≥2|A| \ge2 for every A∈AA \in\mathcal{A}. The empty set cannot belong to A\mathcal{A}, since A\mathcal{A} is an antichain with more than one member.

Suppose that Ai={t}A_i = \{t\}. Every other lower set omits tt, by the antichain property. Delete AiA_i and its two upper neighbors. Each remaining upper set is the union of two remaining lower sets, so it also omits tt. The resulting induced alternating path therefore lies on the seven-element ground set Ω8∖{t}\Omega_8 \setminus\{t\} and has N−1≥24N-1 \ge24 lower vertices, contradicting Lemma 3.3. Thus ∣A∣≥2|A| \ge2 for every A∈AA \in\mathcal{A}.

Apply this lower bound to the complement-dual cycle from Lemma 2.3. Its lower sets are the complements of the original upper sets. Consequently,

8−∣B∣≥2,so∣B∣≤6(B∈B).8-|B| \ge2,\qquad\text{so}\qquad|B| \le6\quad(B \in\mathcal{B}).

Every lower set AA has an upper neighbor BB with A⊂BA \subset B. Hence

∣A∣≤∣B∣−1≤5.|A| \le|B|-1 \le5.

Finally, every upper set BB has a lower neighbor AA with A⊂BA \subset B. Using the lower bound already proved gives

∣B∣≥∣A∣+1≥3.|B| \ge|A|+1 \ge3.

Together, these bounds yield

2≤∣A∣≤5(A∈A),3≤∣B∣≤6(B∈B).2 \le|A| \le5\quad(A \in\mathcal{A}),\qquad3 \le|B| \le6\quad(B \in\mathcal{B}).

□\square

The common penalty budget

For the ranks in (13), define the integer penalty

p(a,b)=1680(w8(a,b)−180).(14)p(a,b)=1680\left(w_8(a,b)-\frac{1}{80}\right). \tag*{(14)}

Lemma 3.2 proves p(a,b)≥0p(a,b) \ge0 analytically. For example,

w8(3,4)=1112+1140−1280=180.w_8(3,4)=\frac{1}{112}+\frac{1}{140}-\frac{1}{280}=\frac{1}{80}.

Substitution in (8), using w8(a,b)=w8(8−b,8−a)w_8(a,b)=w_8(8-b,8-a), gives the complete exact penalty table

(a,b)(a,b)(2,3)(2,3)(2,4)(2,4)(2,5)(2,5)(2,6)(2,6)(3,4)(3,4)(3,5)(3,5)(3,6)(3,6)(4,5)(4,5)(4,6)(4,6)(5,6)(5,6)
p(a,b)p(a,b)14172135062101714

Table 15.

These are rational identities, rather than numerical approximations.

There are 2N2N inclusion edges. Subtracting their baseline contribution 2N/802N/80 from (9) and multiplying by 1680 gives

∑(A,B)∈Ep(∣A∣,∣B∣)≤1680−42N=42(40−N).(15)\sum_{(A,B)\in E} p(|A|,|B|) \le1680-42N=42(40-N). \tag*{(15)}

This is the common counting budget for 35≤N≤4035 \le N \le40.

If ee counts lower sets of sizes 2, 5, each of its two incident edges has penalty at least 14. The same assertion holds if ee instead counts upper sets of sizes 3, 6. For either family separately,

28e≤1680−42N⟺2e+3N≤120.(16)28e \le1680-42N \Longleftrightarrow2e+3N \le120. \tag*{(16)}

The analytic exclusion of order 40

The nonnegative penalties in (16) already give N≤40N \le40. We now exclude the equality case. This section uses only the chain identity and a graph argument; none of the finite refutations is needed.

A seven-vertex graph obstruction

Lemma 4.1. There is no triangle-free graph GG on seven vertices such that ∣NG(u)∪NG(v)∣=2|N_G(u) \cup N_G(v)| = 2 for every nonadjacent pair u,vu,v.

Proof. First, every vertex has degree at most two. Indeed, if a vertex uu had degree at least three, any nonneighbor vv would satisfy ∣N(u)∪N(v)∣≥3|N(u) \cup N(v)| \ge3. Thus uu would have to be universal. Triangle-freeness would then make the other six vertices independent, and two of them would have a common singleton neighborhood, again contradicting the required value two.

Next, there are no isolated vertices. If zz were isolated, the condition applied to zz and any other vertex vv would give deg⁡(v)=2\deg(v) = 2. The other six vertices would form a triangle-free 2-regular graph, necessarily a 6-cycle. Two vertices at distance two in that cycle have a neighborhood union of size three, a contradiction.

It remains to show that GG is connected. Suppose it were disconnected. If one component contained a degree-two vertex uu, choose a vertex vv from another component. There are no isolated vertices, so deg⁡(v)≥1\deg(v) \ge1. The neighborhoods of uu and vv lie in different components, and hence

∣N(u)∪N(v)∣=deg⁡(u)+deg⁡(v)≥3,|N(u) \cup N(v)| = \deg(u) + \deg(v) \ge3,

a contradiction. Therefore every vertex in a disconnected GG would have degree one. Such a graph is a disjoint union of edges and cannot have seven vertices. Thus GG is connected.

A connected graph on seven vertices with maximum degree two is a path P7P_7 or a cycle C7C_7. Each contains two degree-two vertices at distance two whose neighborhood union has size three. This final contradiction proves the lemma.

Excluding equality in the chain bound

Proposition 4.2 (Analytic length bound). A saturated inclusion cycle on eight coordinates has at most 39 lower vertices.

Proof. For N<25N < 25 there is nothing to prove. Otherwise, the rank bounds and nonnegative penalties in (16) give N≤40N \le40.

Suppose N=40N = 40. The chain budget is then zero. Its zero-penalty edge types are (3,4)(3,4) and (4,5)(4,5), so connectedness forces one homogeneous type. After complement duality, assume that the lower family A\mathcal{A} consists of 40 four-sets and the upper family B\mathcal{B} of 40 five-sets.

The chain identity now has value 40/40=140/40 = 1. Every maximal chain must therefore meet A∪B\mathcal{A} \cup\mathcal{B}. In particular, a four-set outside A\mathcal{A} cannot be contained in a five-set outside B\mathcal{B}: a maximal chain through that pair would meet neither selected family.

Let F\mathcal{F} be the family of triples complementary to the five-sets outside B\mathcal{B}. Let H\mathcal{H} be the family of four-sets complementary to members of A\mathcal{A}. If Q∈HQ \in\mathcal{H}, its complement is a selected four-set, which has exactly two selected five-set supersets out of its four supersets. Thus QQ contains exactly two members of F\mathcal{F}. If Q∉HQ \notin\mathcal{H}, all four supersets of its complement are selected five-sets, so it contains no member of F\mathcal{F}. Every four-set consequently contains either zero or two members of F\mathcal{F}, and belongs to H\mathcal{H} exactly in the latter case.

Also, every triple T∉FT \notin\mathcal{F} is contained in exactly two members of H\mathcal{H}: its complementary five-set belongs to B\mathcal{B} and has exactly two selected lower neighbors. Fix a coordinate vv and form a graph on the other seven coordinates, with edge abab when {v,a,b}∈F\{v,a,b\} \in\mathcal{F}. This graph is triangle-free, since a triangle would give a four-set containing at least three members of F\mathcal{F}.

For a nonedge abab, the triple {v,a,b}\{v,a,b\} is not in F\mathcal{F}. For each remaining coordinate xx, the four-set {v,a,b,x}\{v,a,b,x\} belongs to H\mathcal{H} precisely when axax or bxbx is an edge. Indeed, if neither is an edge, its only possible member of F\mathcal{F} is {a,b,x}\{a,b,x\}, and the zero-or-two rule forces zero. If at least one is an edge, the same rule forces two.

Since {v,a,b}\{v,a,b\} has exactly two extensions in H\mathcal{H}, the graph satisfies

∣N(a)∪N(b)∣=2\lvert N(a) \cup N(b) \rvert= 2

for every nonedge. This contradicts the lemma.

Reduction to fifteen finite exclusions

Selection formulas and valid proper-cycle clauses

The remaining exclusions use selection formulas with 35≤∣A∣,∣B∣≤4035 \leq\lvert A\rvert, \lvert B\rvert\leq40. Each selected vertex has degree two, so the two selected cardinalities are equal. Write their common value as NN. Keeping N=40N = 40 is a harmless relaxation of the analytic length bound and preserves the saved CNFs.

Each candidate set has a Boolean variable recording whether it is selected. A conjunctive normal form (CNF) formula is a conjunction of clauses, each a disjunction of literals. A checked refutation proves that no assignment satisfies all clauses. We use reverse-unit-propagation (RUP) refutations, whose checking rule is given in Section S4 of the Supplementary Material.

The formulas impose the antichain and saturation conditions, the stage-specific restrictions proved below, and valid clauses excluding short cycle components. They need not impose full connectedness. Section S1 of the Supplementary Material constructs twenty-one proper-cycle representatives; Section S2 specifies all encodings. The next lemma justifies their use without any prior solver verdict.

Lemma 5.1 (Proper-cycle clause). Let zvz_v indicate selection of a set-vertex. If CC is an induced alternating cycle with fewer than 70 vertices in the strict-inclusion graph, every induced 2N2N-cycle with N≥35N \geq35 satisfies

⋁v∈C¬zv(17)\bigvee_{v \in C} \neg z_v \tag*{(17)}

The same holds for every coordinate-permuted copy of CC.

Proof. If all vertices of CC were selected, each would already have two selected neighbors in CC. The degree-two constraints would preclude any edge to the remaining selected vertices. Thus CC would be a proper connected component, contradicting connectedness of the target cycle. Coordinate permutations preserve inclusion.

The formula names distinguish local branches, not polygon orders. The following observation links each finite refutation to the covering problem.

Lemma 5.2 (From a cycle to a formula). Fix a normalized local branch. A target cycle satisfying its established rank restrictions, orientation, and counting inequalities extends to a satisfying assignment of the corresponding selection formula. Consequently, a checked refutation of that formula excludes the branch.

Proof. Select exactly the target vertices. Their antichain, degree, and saturation identities satisfy the base clauses; normalization satisfies the fixed-vertex clauses. Pruning uses only these conditions and prior rank exclusions, so it removes no target vertex. The hypotheses give the counting and orientation constraints, and Lemma 5.1 gives the proper-cycle clauses. The encodings in Section S2 of the Supplementary Material then provide the auxiliary values. A refutation excludes this satisfying assignment.

Stage H: excluding homogeneous cycles

For a homogeneous cycle of type (2,3)(2,3) or (5,6)(5,6), the extreme count in (16) is e=Ne=N, giving 5N≤1205N \le120, impossible here. Together with the rank restrictions, this leaves the homogeneous types (3,4)(3,4) and (4,5)(4,5). Complement duality reduces them to (4,5)(4,5).

Lemma 5.3 (Five homogeneous branches). Every homogeneous cycle of type (4,5)(4,5) with N>5N > 5 lower vertices can be relabeled so that its first three lower sets are

A0={0,1,2,3},A1={0,1,2,4},A2={0,1,4,5}.(18)A_0 = \{0,1,2,3\}, \qquad A_1 = \{0,1,2,4\}, \qquad A_2 = \{0,1,4,5\}. \tag*{(18)}

Its fourth set is (A2∖{r})∪{s}(A_2 \setminus\{r\}) \cup\{s\}, where the pair (r,s)(r,s) can be chosen from

(4,3),(1,3),(5,6),(4,6),(1,6).(19)(4,3), \quad(1,3), \quad(5,6), \quad(4,6), \quad(1,6). \tag*{(19)}

Proof. The intersection of three consecutive lower sets has size two or three. If every such intersection had size three, start with the three-element intersection of two consecutive lower sets. Each successive triple condition preserves this same intersection. All lower sets would contain a common three-element core, giving at most 8−3=58 - 3 = 5 distinct lower sets, a contradiction.

Choose a triple whose intersection has size two. Normalize the first two sets to {0,1,2,3}\{0,1,2,3\} and {0,1,2,4}\{0,1,2,4\}. The third deletes one of their common elements and adds an element outside their union. Adding the previously deleted element 3 instead would repeat the upper union, which is impossible. A coordinate permutation therefore gives (18).

Write the fourth set as

A3=(A2∖{r})∪{s},r∈{0,1,4,5},s∈{2,3,6,7}.A_3 = (A_2 \setminus\{r\}) \cup\{s\}, \qquad r \in\{0,1,4,5\}, \qquad s \in\{2,3,6,7\}.

The earlier upper set B1={0,1,2,4,5}B_1 = \{0,1,2,4,5\} would contain A3A_3 if s=2s = 2, so this value is forbidden. For s∈{3,6,7}s \in\{3,6,7\}, the new upper union A2∪{s}A_2 \cup\{s\} omits coordinate 2 and therefore contains neither A0A_0 nor A1A_1. The only further obstruction is containment in B0={0,1,2,3,4}B_0 = \{0,1,2,3,4\}: it occurs precisely when (r,s)=(5,3)(r,s) = (5,3). Thus the complete condition is

s∈{3,6,7},(r,s)≠(5,3).(20)s \in\{3,6,7\}, \qquad(r,s) \ne(5,3). \tag*{(20)}

The prefix stabilizer independently swaps 0, 1 and 6, 7. For s=3s = 3, it distinguishes deletion of a core element from deletion of 4; deletion of 5 is forbidden. For s∈{6,7}s \in\{6,7\}, it distinguishes deletion of a core element, of 4, and of 5. This gives exactly five orbits, represented by (19).

Lemma 5.4 (Computational lemma H). For 35≤N≤4035 \le N \le40, no homogeneous saturated inclusion cycle of type (4,5)(4,5) exists on eight coordinates.

Proof. For each of the five branches in (19), fix the four lower sets and their three consecutive upper unions. Use all four-sets as lower candidates and all five-sets as upper candidates, with selection sizes between 35 and 40, and impose the base clauses and the proper-cycle clauses described above.

These are the formulas H43, H57, H83, H99, and H113. Each has a checked RUP refutation; their sizes and proof lengths are recorded in Table S2 of the Supplementary Material. Lemma 5.3 covers all possibilities.

CaseVariablesInitial clausesChecked RUP additions
H435,15838,915316,971
H575,15838,915325,151
H835,15838,915430,293
H995,15838,915206,040
H1135,15838,915285,331
G2342,272104,461339,780
G2546,372115,028501,582
G2643,730105,857132,152
T113,40233,49831,624
T218,44447,655270,546
T318,03246,516254,984
M027,35569,151778,136
M226,80771,852523,646
F3526,37570,9571,070,069
F3726,37571,0721,557,558

Table S2. Uniform exclusions for 35≤N≤4035\leq N\leq40.

Complement duality also excludes the homogeneous type (3,4)(3,4).

Stage G: restricting the possible rank pairs

We next exclude three rank pairs and their duals. These exclusions also sharpen the counting budget for the subsequent stages.

Lemma 5.5 (Computational lemma G). A saturated inclusion cycle with 35≤N≤4035 \le N \le40 lower vertices has no edge of type (2,3)(2,3), (2,5)(2,5), or (2,6)(2,6).

Proof. For each chosen type (2,s)(2,s), normalize its edge to

A={0,1}⊂B={0,…,s−1}.A = \{0,1\} \subset B = \{0,\ldots,s-1\}.

The other lower neighbor CC of BB satisfies A∪C=BA \cup C = B. Thus

C=(B∖A)∪XC = (B \setminus A) \cup X

with XX a proper subset of AA. The lower rank bound and the swap of 0 and 1 give these representatives:

(2,s)(2,s)B∖AB \setminus AXX
(2,3)(2,3){2}\{2\}{0}\{0\}
(2,5)(2,5){2,3,4}\{2,3,4\}∅\varnothing or {0}\{0\}
(2,6)(2,6){2,3,4,5}\{2,3,4,5\}∅\varnothing or {0}\{0\}

Table 22.

Use the full rank ranges (13), fix the chosen edge, require at least one of these representative neighbors, and impose the base clauses, (17), and the proper-cycle clauses. The resulting formulas G23, G25, and G26 each have a checked RUP refutation. The normalization uses only the set ranks, so it is valid uniformly in NN.

Corollary 5.6. Every remaining saturated inclusion cycle has lower ranks in {2,3,4}\{2,3,4\} and upper ranks in {4,5,6}\{4,5,6\}. Its possible edge types are exactly among

(2,4), (3,4), (3,5), (4,5), (4,6).(21)(2,4),\ (3,4),\ (3,5),\ (4,5),\ (4,6). \tag*{(21)}

Proof. Complement duality also excludes (5,6)(5,6) and (3,6)(3,6). A lower set of size five could only have upper neighbors of size six, and an upper set of size three could only have lower neighbors of size two. Both are impossible by these exclusions. The remaining strict rank pairs give (23).

Let x,a,ux,a,u count lower sets of sizes 2, 3, 4, and let b,zb,z count upper sets of sizes 4, 6, respectively. Then N=x+a+uN=x+a+u. Write tt for the number of (3,5)(3,5) edges. All 2x2x edges incident with lower two-sets end at upper four-sets. Consequently the number of (3,4)(3,4) edges is 2b−2x2b-2x, and counting at lower three-sets gives

t=2a−(2b−2x)=2(a−b+x).(22)t = 2a - (2b - 2x) = 2(a-b+x). \tag*{(22)}

The only nonzero penalties among (23) are 17 on (2,4),(4,6)(2,4),(4,6) and 6 on (3,5).(3,5). Therefore

34(x+z)+6t≤1680−42N,(23)34(x+z) + 6t \le1680 - 42N, \tag*{(23)}
23x+17z+6a−6b+21N≤840,(24)23x + 17z + 6a - 6b + 21N \le840, \tag*{(24)}
44x+27a+21u+17z−6b≤840.(25)44x + 27a + 21u + 17z - 6b \le840. \tag*{(25)}

The last identity uses N=x+a+uN=x+a+u. It is the constant-right-hand-side weighted constraint used in the uniform formulas. Since t≥0t \ge0 and N≥35N \ge35, the first inequality also gives

x+z≤6.(26)x+z \le6. \tag*{(26)}

Stage T: removing lower two-sets and upper six-sets

After GG, the extreme ranks are lower two-sets and upper six-sets. Duality permits us to anchor at a lower two-set. One of its four local branches is excluded by the following shadow argument; the other three are excluded by checked refutations.

Lemma 5.7 (Three disjoint pairs). Suppose an inclusion cycle in 2Ω82^{\Omega_8} has all upper ranks at least four. If its lower family contains three pairwise disjoint two-element sets, then its upper family has at most 34 members.

Proof. Let the three pairs be P0P_0, P1P_1, P2P_2. Split the upper family into X\mathcal{X}, whose members contain at least one PiP_i, and Y\mathcal{Y}, whose members contain none. Each PiP_i has exactly two upper neighbors, so there are six pair–upper incidences and ∣X∣≤6|\mathcal{X}| \le6.

A set avoiding all three pairs chooses at most one element from each pair and can also use either of the two remaining coordinates. Its size is at most five. The number of such four-sets is

23(21)+(32)22=16+12=28.(27)2^3 \binom{2}{1}+\binom{3}{2}2^2=16+12=28. \tag*{(27)}

The first term uses all three pairs and one remaining coordinate; the second uses two pairs and both remaining coordinates.

Write Yj\mathcal{Y}_j for the members of Y\mathcal{Y} of size jj. Let Δ\Delta be the family of four-subsets of members of Y5\mathcal{Y}_5. Every member of Y5\mathcal{Y}_5 has five such subsets. Each such four-set extends to at most two such five-sets. If it uses all three pairs, only the second free coordinate can be added. If it uses two pairs, either element of the missing pair can be added. Counting containments gives

5∣Y5∣≤2∣Δ∣.5|\mathcal{Y}_5|\le2|\Delta|.

Since the upper family is an antichain, Y4∩Δ=∅\mathcal{Y}_4\cap\Delta=\varnothing. Therefore

∣Y∣≤28−∣Δ∣+∣Y5∣≤28−32∣Y5∣≤28.(28)|\mathcal{Y}|\le28-|\Delta|+|\mathcal{Y}_5|\le28-\frac{3}{2}|\mathcal{Y}_5|\le28. \tag*{(28)}

It follows that

∣B∣=∣X∣+∣Y∣≤6+28=34.|\mathcal{B}|=|\mathcal{X}|+|\mathcal{Y}|\le6+28=34.

:::

Lemma 5.8 (Four local branches). If x+z>0x+z>0, complement duality permits x≥zx\ge z. After relabeling, a five-vertex subpath has the form

P1∪X,P0∪P1,P0,P0∪P2,P2∪Y,(29)P_1\cup X,\quad P_0\cup P_1,\quad P_0,\quad P_0\cup P_2,\quad P_2\cup Y, \tag*{(29)}

where

P0={0,1},P1={2,3},P2={4,5},P_0=\{0,1\},\qquad P_1=\{2,3\},\qquad P_2=\{4,5\},

and

branchXYT0∅∅T1∅{0}T2{0}{0}T3{0}{1}(30)\begin{array}{c|cc} \text{branch} & X & Y\\ T_0 & \varnothing& \varnothing\\ T_1 & \varnothing& \{0\}\\ T_2 & \{0\} & \{0\}\\ T_3 & \{0\} & \{1\} \tag*{(30)} \end{array}

Proof. Duality exchanges xx and zz, so choose x≥zx\ge z. Then x≥1x\ge1. Fix a two-element lower set P0P_0. Both upper neighbors have size four, and their intersection is precisely P0P_0. Their two-element parts outside P0P_0 are therefore disjoint; call them P1,P2P_1,P_2. By the union identity, the other lower neighbor on each side is P1∪XP_1 \cup X or P2∪YP_2 \cup Y, where X,YX,Y are empty or singleton subsets of P0P_0.

Up to simultaneously exchanging 0 and 1 and reversing the path, the complete possibilities are: both empty; exactly one empty; two equal singletons; or two distinct singletons. These give the four rows of (30).

Lemma 5.9 (Computational lemma T). Every remaining saturated inclusion cycle has x=z=0x=z=0.

Proof. If x+z>0x+z>0, choose complement orientation x≥zx \ge z and apply Lemma 5.8. Branch T0_0 contains three pairwise disjoint lower pairs, contradicting Lemma 5.7 because N≥35N \ge35.

For each other branch, fix its five-vertex path and use the remaining rank pairs, the base and proper-cycle clauses, (25), (26), and x≥zx \ge z. The three formulas T1, T2, and T3 have checked RUP refutations. Thus none of the four branches occurs.

Stage M: proving that mixed edges form a matching

Only lower ranks 3, 4 and upper ranks 4, 5 remain. Call an edge of type (3,5)(3,5) mixed. If there were no mixed edge, connectedness would force a homogeneous type (3,4)(3,4) or (4,5)(4,5), contrary to Lemma 5.4 and duality. Hence t>0t>0, and

t=2(a−b),6t≤1680−42N.(31)t=2(a-b), \qquad6t \le1680-42N. \tag*{(31)}

All preceding exclusions are preserved by complement duality. Under this duality, (a,b)(a,b) becomes (N−b,N−a)(N-b,N-a). Choose the orientation

a+b≤N,equivalentlyb≤u.(32)a+b \le N, \qquad\text{equivalently} \qquad b \le u. \tag*{(32)}

This choice precedes the local normalization, which uses only coordinate permutations. The whole cycle cannot be mixed: t=2Nt=2N would imply 54N≤168054N \le1680, contrary to N≥35N \ge35.

Lemma 5.10 (Three boundary branches). In a cycle satisfying (32), a mixed edge can be chosen and normalized as

A={0,1,2}⊂B={0,1,2,3,4}.A=\{0,1,2\} \subset B=\{0,1,2,3,4\}.

Let CC be the other lower neighbor of BB and DD the other upper neighbor of AA. Write

C={3,4}∪X,D=A∪Y.C=\{3,4\}\cup X, \qquad D=A\cup Y.

Then the three possible branches have representatives

branchXXYY
M0_0{0}\{0\}{5}\{5\}
M1_1{0,1}\{0,1\}{5}\{5\}
M2_2{0,1}\{0,1\}{5,6}\{5,6\}

Table 35.

Proof. By (31), mixed edges do not occupy the entire 2N2N-cycle. Choose a mixed edge at a boundary of a maximal run of mixed edges. At least one of its adjacent edges is not mixed.

Normalize A={0,1,2}A=\{0,1,2\} and B={0,1,2,3,4}B=\{0,1,2,3,4\}. The union identity requires that CC contain {3,4}\{3,4\} and either one or two elements of AA. The intersection identity requires that DD be AA together with either one or two elements of {5,6,7}\{5,6,7\}. The core coordinates and the outside coordinates may be permuted independently.

If ∣C∣=3|C|=3 and ∣D∣=5|D|=5, both adjacent edges are mixed, contrary to the boundary choice. For each remaining pair of sizes, the independent permutations of AA and {5,6,7}\{5,6,7\} act transitively on the choices. The three size pairs therefore give exactly the representatives in (35).

The budget and orientation yield three further necessary bounds:

1≤a−b≤17,a≤26,b≤19.(33)1 \le a-b \le17,\qquad a \le26,\qquad b \le19. \tag*{(33)}

Indeed, t=2(a−b)>0t=2(a-b)>0 and

6(a−b)+21N≤8406(a-b)+21N \le840

give the first bounds. Since b≤N−ab \le N-a, the same inequality gives

12a+15N≤840,12a+15N \le840,

and N≥35N \ge35 gives a≤26a \le26. Finally, a≥b+1a \ge b+1 and a+b≤N≤40a+b \le N \le40 imply b≤19b \le19. These consequences are valid before imposing any matching condition.

Lemma 5.11 (Computational lemma M). Neither boundary branch M0\mathrm{M}_0 nor M2\mathrm{M}_2 occurs in a remaining cycle satisfying (32).

Proof. Use lower ranks 3, 4 and upper ranks 4, 5, and fix the four vertices of the indicated normalized branch. Impose the base and proper-cycle clauses, (27) with x=z=0x=z=0, (34), and (36). The formulas M0 and M2 have checked RUP refutations.

Corollary 5.12. The mixed edges of a remaining cycle form a nonempty matching.

Proof. If a maximal run of mixed edges had length at least two, consider an endpoint mixed edge of that run. If its nonmixed neighbor is incident with its lower endpoint, then ∣D∣=4|D|=4 and ∣C∣=3|C|=3, giving M0. If the nonmixed neighbor is incident with its upper endpoint, then ∣C∣=4|C|=4 and ∣D∣=5|D|=5, giving M2. Both are impossible by Lemma 5.11. A run occupying the entire cycle has already been excluded by (31). Thus every run has length one. Nonemptiness was proved above.

In particular, it is now valid to require that a selected rank-three lower set have at most one selected rank-five upper neighbor, and that a selected rank-five upper set have at most one selected rank-three lower neighbor. These additional constraints depend on both refutations in Lemma 5.11; they are not assumptions used in proving that lemma.

Stage F: excluding the final two branches

The matching property has now been proved. It reduces the neighborhood of any mixed edge to the following two possibilities.

Lemma 5.13 (Two final branches). A remaining cycle can be normalized to contain lower sets

A={0,1,2},C={0,1,3,4}A=\{0,1,2\},\qquad C=\{0,1,3,4\}

and upper sets

B={0,1,2,3,4},D={0,1,2,5}.B=\{0,1,2,3,4\},\qquad D=\{0,1,2,5\}.

The other lower neighbor EE of DD can be chosen as {0,1,5}\{0,1,5\} or {0,2,5}\{0,2,5\}.

Proof. Choose any mixed edge. By Corollary 5.12, its adjacent edges are both nonmixed. It is therefore in branch M1, so normalize its four sets as in (35).

The other lower neighbor EE of DD has size three and satisfies A∪E=DA \cup E=D. Its possibilities are exactly

{0,1,5},{0,2,5},{1,2,5}.\{0,1,5\},\qquad\{0,2,5\},\qquad\{1,2,5\}.

The swap 0↔10 \leftrightarrow1 fixes AA, BB, CC, DD, fixes the first possibility, and exchanges the last two. Thus two representatives suffice.

Lemma 5.14 (Computational lemma F). Neither final branch in Lemma 5.13 occurs.

Proof. For E={0,1,5}E = \{0,1,5\} or E={0,2,5}E = \{0,2,5\}, fix the five normalized vertices. Use the M-stage constraints and additionally require the mixed edges to form a matching, as justified by Corollary 5.12. For a vertex vv and two of its mixed neighbors r,sr,s, this last condition is the clause

¬zv∨¬zr∨¬zs.\lnot z_v \lor\lnot z_r \lor\lnot z_s.

The two formulas F35 and F37 have checked RUP refutations. The suffixes are the decimal masks of EE, not matrix orders.

Completion of the main proof

Proof of Theorem 1.2. Suppose 35≤n≤4035 \le n \le40 and a covering by at most eight rectangles exists. We apply the reductions in the order described in § 1.4.

Step 1: normalization and the analytic bound. Pad the covering with empty rectangles and apply Lemma 2.1. The resulting saturated inclusion cycle has N=nN = n lower vertices. Proposition 3.4 gives its rank ranges, and (15) gives its penalty budget. Proposition 4.2 gives N≤39N \le39, leaving only 35≤N≤3935 \le N \le39.

Step 2: the H, G, and T exclusions. Lemma 5.4 and duality exclude both homogeneous types. Lemma 5.5 and duality leave the five rank pairs in (21). Lemma 5.7 and the three T refutations then give x=z=0x = z = 0 by Lemma 5.9. Thus the lower ranks are 3, 4 and the upper ranks are 4, 5.

Step 3: the M exclusions. Since the cycle is not homogeneous, it contains a mixed edge. Choose the dual orientation (32). Lemma 5.11 excludes the two boundary branches that would allow adjacent mixed edges. Corollary 5.12 therefore gives a nonempty matching of mixed edges.

Step 4: the final contradiction. Lemma 5.13 reduces a neighborhood of a mixed edge to one of two F branches. Both are excluded by Lemma 5.14. Every finite exclusion is applicable by Lemma 5.2, using only the conditions established before that stage.

The assumed covering cannot exist, so RCB⁡(Mn)≥9\operatorname{RCB}(M_n) \ge9. Proposition 1.1 supplies the published upper bound RCB⁡(Mn)≤9\operatorname{RCB}(M_n) \le9. Since rectangle covering number depends only on the support, the same equality holds for SPS_P.

Certificates and supplementary material

All fifteen CNFs were reconstructed byte for byte. A RUP implementation separate from the solver checked their refutations through an empty clause, verifying 7,023,863 additions in total. Lemma 5.2 and the local classifications give the mathematical reduction; the refutations give the finite exclusions. The analytic bound in Proposition 4.2 uses none of these refutations.

The accompanying Supplementary Material provides the proper-cycle constructions and complete parameters in Section S1, the exact encodings in Section S2, the certificate inventory in Section S3, checking methods and commands in Section S4, and the published upper-bound witnesses in Section S5. It is supplied together with this paper and the certificate archive. The checks reported here do not assert a third-party audit or a proof-assistant formalization.

The certificate archive are available at https://doi.org/10.5281/zenodo.23837747.

Declaration of generative-AI assistance

An OpenAI language model accessed through Codex assisted with the programs, certificate workflow, and writing. Its assertions were not treated as certificates. The finite exclusions were checked by the supplied RUP implementation.

References

Supplementary Material

This supplement accompanies the main paper of the same title and is provided as part of its proof record. It collects the complete proper-cycle parameters, encoding details, certificate inventory, checking procedures, and published upper-bound witnesses. The main paper retains the key mathematical lemmas and local classification proofs. Neither source requires the other document’s auxiliary files for compilation.

We use MnM_n for the zero–one matrix whose zeros are (j,j)(j,j) and (j+1,j)(j+1,j) modulo nn. A saturated inclusion cycle consists of two antichains A={Ai}\mathcal{A}=\{A_i\} and B={Bj}\mathcal{B}=\{B_j\} satisfying

Bj=Aj∪Aj+1,Ai=Bi−1∩Bi,Ai⊆Bj⟺i∈{j,j+1}.B_j=A_j\cup A_{j+1},\qquad A_i=B_{i-1}\cap B_i,\qquad A_i\subseteq B_j\Longleftrightarrow i\in\{j,j+1\}.

The saved formulas use Ω8={0,…,7}\Omega_8=\{0,\ldots,7\} and allow N=∣A∣=∣B∣N=|\mathcal{A}|=|\mathcal{B}| with 35≤N≤4035\leq N\leq40. The analytic length bound in the main paper excludes N=40N=40 without a refutation. Keeping this value in the formulas is a harmless relaxation and preserves the originally checked CNFs.

Proper-cycle constructions and complete parameters

The proper-cycle clauses belong to the initial CNFs. They must therefore be justified independently of any solver verdict. The following three constructions establish the validity of every supplied representative without testing its incidence matrix.

Why proper-cycle clauses are valid

Lemma S1.1 (Proper-cycle clause). Let zvz_v indicate selection of a set-vertex. If CC is an induced alternating cycle with fewer than 70 vertices in the strict-inclusion graph, every induced 2N2N-cycle with N≥35N\geq35 satisfies

⋁v∈C¬zv.(34)\bigvee_{v\in C}\neg z_v. \tag*{(34)}

The same holds for every coordinate-permuted copy of CC.

Proof. If all vertices of CC were selected, each would already have two selected neighbors in CC. The degree-two constraints would preclude any edge to the remaining selected vertices. Thus CC would be a proper connected component, contradicting connectedness of the target cycle. Coordinate permutations preserve inclusion.

General cycle constructions

Lemma S1.2 (Cyclic intervals). Let u0,…,um−1u_0,\ldots,u_{m-1} be distinct coordinates, let TT be disjoint from them, and let 1≤s≤m−21\leq s\leq m-2. With indices modulo mm, define

Li=T∪{ui,…,ui+s−1},Ui=T∪{ui,…,ui+s}.L_i=T\cup\{u_i,\ldots,u_{i+s-1}\},\qquad U_i=T\cup\{u_i,\ldots,u_{i+s}\}.

Then (Li,Ui)(L_i,U_i) is a saturated inclusion cycle. Denote this construction by Im,s(T;u0,…,um−1)I_{m,s}(T;u_0,\ldots,u_{m-1}).

Proof. The union and intersection identities follow from consecutive intervals and s≤m−2s\leq m-2. To check inclusion, fix jj and regard {uj,…,uj+s}\{u_j,\ldots,u_{j+s}\} as a proper arc of the cyclic order. A consecutive ss-element interval contained in this arc can start only at uju_j or uj+1u_{j+1}. A later start would meet uj+s+1u_{j+s+1}, which is outside the arc; a start outside the arc is immediately excluded. Hence Li⊆UjL_i\subseteq U_j exactly when i=ji=j or j+1j+1.

Lemma S1.3 (Subdivision using fresh coordinates). Suppose consecutive lower sets in a saturated inclusion cycle are P∪{r}P \cup\{r\} and P∪{s}P \cup\{s\}, with r≠sr \ne s outside PP. For fresh coordinates z1,…,zqz_1,\ldots,z_q absent from every old set, replace this adjacency by the lower-set path

P∪{r},P∪{z1},…,P∪{zq},P∪{s},P \cup\{r\},\quad P \cup\{z_1\},\ldots,P \cup\{z_q\},\quad P \cup\{s\},

and use consecutive unions as the new upper sets. The result is again a saturated inclusion cycle.

Proof. Each new lower set contains a fresh coordinate and therefore lies in no old upper set. Each new upper set contains either two fresh coordinates or one fresh coordinate and one of r,sr,s. An old lower set contained in it would consequently lie in PP, P∪{r}P \cup\{r\}, or P∪{s}P \cup\{s\}. The antichain property allows only the appropriate endpoint in the latter two cases and no old lower set in the first. Among new sets, the fresh coordinate specifies exactly the two incident upper sets. Union and intersection identities hold along the path, and at its endpoints they follow because old sets omit the fresh coordinates. All other incidences are unchanged. □\square

The H representatives

For the only subdivision pattern needed here, take eight distinct coordinates in the order (t,a,b,c,d,e,x,y)(t,a,b,c,d,e,x,y), put T={t}T=\{t\}, and use the cyclic sequence

T∪{a,x,y},T∪{b,x,y},T∪{c,x,y},T∪{c,d,x},T∪{c,d,e},T∪{d,e,y},T∪{e,x,y}.(35)\begin{aligned} &T \cup\{a,x,y\},\quad T \cup\{b,x,y\},\quad T \cup\{c,x,y\},\quad T \cup\{c,d,x\},\\ &T \cup\{c,d,e\},\quad T \cup\{d,e,y\},\quad T \cup\{e,x,y\}. \tag*{(35)} \end{aligned}

Call it E(t,a,b,c,d,e,x,y)E(t,a,b,c,d,e,x,y). Start with I5,3({t};y,x,c,d,e)I_{5,3}(\{t\};y,x,c,d,e) and subdivide the adjacency between T∪{e,x,y}T \cup\{e,x,y\} and T∪{c,x,y}T \cup\{c,x,y\} using the fresh coordinates a,ba,b. Lemma S1.3 proves (S1.2).

Table S1 gives exact construction parameters for all seventeen H representatives. In an II row the third column is TT and the fourth is the ordered cyclic list of uu coordinates. In an EE row the fourth column is (t,a,b,c,d,e,x,y)(t,a,b,c,d,e,x,y). Substitution yields the same selected lower and upper sets as the saved representatives, up to rotation or reversal of their listing. The full coordinate orbits, and therefore their proper-cycle clauses, are unchanged.

IDConstructionCore TTOrdered coordinates
H43.1I5,1I_{5,1}{2,3,5}\{2,3,5\}0, 4, 1, 6, 7
H43.2EE–6, 4, 3, 7, 1, 2, 5, 0
H43.3I5,3I_{5,3}{1}\{1\}0, 4, 7, 3, 6
H57.1EE–0, 1, 3, 7, 4, 2, 5, 6
H57.2I7,3I_{7,3}{7}\{7\}0, 4, 2, 3, 1, 6, 5
H57.3I5,3I_{5,3}{0}\{0\}1, 2, 3, 5, 4
H57.4I5,1I_{5,1}{2,4,6}\{2,4,6\}0, 5, 1, 3, 7
H83.1I5,2I_{5,2}{2,4}\{2,4\}0, 6, 5, 3, 7
H83.2I5,3I_{5,3}{0}\{0\}2, 5, 3, 4, 6
H83.3EE–0, 5, 6, 7, 3, 2, 4, 1
H99.1I5,3I_{5,3}{0}\{0\}2, 5, 3, 4, 6
H99.2I7,3I_{7,3}{7}\{7\}0, 3, 2, 5, 6, 1, 4
H99.3I5,1I_{5,1}{2,4,6}\{2,4,6\}0, 5, 1, 3, 7

Table S1. Table S1: Analytic descriptions of all H representatives. Coordinates, unlike decimal masks, are the integers 0 through 7.

IDConstructionCore TTOrdered coordinates
H113.1EE—7, 2, 5, 6, 0, 3, 4, 1
H113.2I5,1I_{5,1}{1,5,7}\{1, 5, 7\}0, 2, 6, 4, 3
H113.3I7,3I_{7,3}{0}\{0\}1, 6, 2, 5, 3, 4, 7
H113.4I5,3I_{5,3}{4}\{4\}1, 2, 6, 5, 7

Table 3.

The Q representatives

Lemma S1.4 (Disjoint petals). Let P0,P1,P2P_0, P_1, P_2 be nonempty pairwise disjoint sets, disjoint from a core TT. The lower sets Li=T∪PiL_i = T \cup P_i and upper sets Ui=T∪Pi∪Pi+1U_i = T \cup P_i \cup P_{i+1}, with indices modulo 33, form a saturated six-vertex inclusion cycle.

Proof. Disjointness and nonemptiness give Li⊆UjL_i \subseteq U_j exactly when i∈{j,j+1}i \in\{j, j+1\}. Taking the indicated unions and intersections recovers UiU_i and LiL_i respectively.

The four Q representatives follow immediately from these petals:

TTP0P_0P1P_1P2P_2
Q1Q_1{0,1}\{0,1\}{2}\{2\}{3}\{3\}{4}\{4\}
Q2Q_2{0,1,2}\{0,1,2\}{3}\{3\}{4}\{4\}{5}\{5\}
Q3Q_3{0,1}\{0,1\}{2}\{2\}{3}\{3\}{4,5}\{4,5\}
Q4Q_4{0}\{0\}{1,2}\{1,2\}{3,4}\{3,4\}{5,6}\{5,6\}

Table 4.

Their lower-mask sequences are respectively (7,11,19)(7, 11, 19), (15,23,39)(15, 23, 39), (7,11,51)(7, 11, 51), and (7,25,97)(7, 25, 97). All fifteen uniform formulas use all twenty-one representatives, together with their coordinate-permuted copies that lie in the retained candidate domain. Each representative has 6, 10, or 14 vertices, so Lemma S1.1 applies for every 35≤N≤4035 \le N \le40. The generators compare the saved data exactly with the parameters above. Thus every proper-cycle clause has a direct mathematical justification.

Selection model and exact encodings

For reference, xx, aa, uu count selected lower sets of sizes 2, 3, 4, and bb, zz count selected upper sets of sizes 4, 6. After the G exclusions, N=x+a+uN = x + a + u. The main paper proves the following constraints, which we restate to specify the encodings without external equation references:

2e+3N≤120.(36)2e + 3N \le120. \tag*{(36)}

Here ee counts lower sets of sizes 2, 5 or, separately, upper sets of sizes 3, 6. After the G exclusions, the weighted constraint is

44x+27a+21u+17z−6b≤840.(37)44x + 27a + 21u + 17z - 6b \le840. \tag*{(37)}

After the T exclusions, the M and F stages have x=z=0x = z = 0 and use the dual orientation a+b≤Na + b \le N, equivalently b≤ub \le u, as well as

1≤a−b≤17,a≤26,b≤19.(38)1 \le a - b \le17,\qquad a \le26,\qquad b \le19. \tag*{(38)}

The matching condition is imposed only at the F stage, after the two M-stage refutations have justified it in the main paper.

Selection variables and saturation

Encode a set S⊆Ω8S \subseteq\Omega_8 by the decimal mask μ(S)=∑t∈S2t\mu(S) = \sum_{t \in S} 2^t. This explains the numerical suffixes of the formula names. For each retained lower or upper candidate introduce a selection variable z(a,S)z_{(a,S)} or z(b,T)z_{(b,T)}. The base clauses impose the following conditions:

  1. Select between 35 and 40 sets in each family.

  1. Do not select two distinct comparable sets in either family, or the same set in both families.

  1. Every selected vertex has exactly two selected permitted strict-inclusion neighbors. For a previously excluded rank pair, prohibit selection of both endpoints.

  1. The two lower neighbors of a selected upper set have that set as their union; the two upper neighbors of a selected lower set have that set as their intersection.

The last requirement has the clauses

¬z(b,T)∨⋁S⊆Tt∈Sz(a,S),t∈T,(39)\neg z_{(b,T)} \lor\bigvee_{\substack{S \subseteq T \\ t \in S}} z_{(a,S)}, \qquad t \in T, \tag*{(39)}
¬z(a,S)∨⋁T⊇St∉Tz(b,T),t∉S.(40)\neg z_{(a,S)} \lor\bigvee_{\substack{T \supseteq S \\ t \notin T}} z_{(b,T)}, \qquad t \notin S. \tag*{(40)}

The disjunctions range over retained permitted neighbors. Together with the degree constraints, they express exactly the required set identities. Cardinality constraints use the sequential-counter encoding supplied by Python-SAT [2]. Every clause of a selected vertex’s neighbor constraint is guarded by the negation of its selection variable. All auxiliary variables are fresh for their respective encodings. If the vertex is unselected, every guarded clause is true. If it is selected, the clauses are precisely an encoding of degree two. Thus guarding preserves the intended conditional constraint.

Pruning removes only candidates forced false by an antichain conflict, a forbidden inclusion rank, or the two neighbors already fixed at a selected vertex. If a forced vertex has only two remaining possible neighbors, both are forced selected. Each recorded step is checked independently. No exact-order cardinality clause from an earlier n=35n = 35 builder is retained: the uniform CNF is constructed afresh with the interval cardinalities stated above.

This construction requires only the implication from a target cycle to a satisfying assignment. A satisfying assignment may describe several components; it need not give a polygon covering. Such extra assignments make unsatisfiability harder to establish and do not invalidate an exclusion.

The G formulas use (S2.1). The T formulas use (S2.2), x+z≤6x + z \leq6, and x≥zx \geq z. The M and F formulas use (S2.2) with x=z=0x = z = 0, a+b≤Na + b \leq N, and (S2.3). Only the F formulas impose the matching condition, after both M refutations have established the matching property in the main paper. The absence of full connectivity clauses makes these formulas relaxations of the target cycle problem; all added proper-cycle clauses are valid by Lemma S1.1. Unsatisfiability of these relaxations therefore suffices.

The weighted encoding

Proposition S2.1. A network of Boolean adders followed by the binary comparison clauses below is an existential CNF encoding of a nonnegative integer weighted inequality ∑jwjvj≤B\sum_j w_j v_j \leq B.

Proof. A half-adder satisfies u+v=s+2cu + v = s + 2c, where s=u⊕vs = u \oplus v and c=u∧vc = u \land v. A full-adder satisfies

u+v+w=s+2c,s=u⊕v⊕w,c=(u∧v)∨(u∧w)∨(v∧w).u + v + w = s + 2c, \qquad s = u \oplus v \oplus w, \qquad c = (u \land v) \lor(u \land w) \lor(v \land w).

The sum output is the parity, and the carry output states whether at least two inputs are one. These identities prove the arithmetic of each gate. Clauses defining the displayed Boolean equivalences give an exact CNF representation of the gate.

Expand each wjw_j in binary and place its input literal vjv_j in the corresponding bit columns. Repeatedly replace two or three column inputs by a sum bit in that column and a carry bit in the next. Summing the gate identities with their powers-of-two weights shows that the resulting binary word SS equals ∑jwjvj\sum_j w_jv_j.

Pad SS and BB with leading zeroes to a common length. For every position ii with Bi=0B_i=0, use the clause

¬Si∨⋁j>iBj=1¬Sj∨⋁j>iBj=0Sj.(41)\neg S_i \lor\bigvee_{\substack{j>i\\B_j=1}} \neg S_j \lor\bigvee_{\substack{j>i\\B_j=0}} S_j . \tag*{(41)}

It forbids Si=1S_i=1 when all more significant bits match BB. If S>BS>B, the highest differing bit violates exactly such a clause. If S≤BS\leq B, every such clause is satisfied, either at position ii or by a higher differing bit. Thus these clauses express S≤BS\leq B. The gate equations determine their auxiliary values from the inputs, proving existential equivalence.

In (S2.2), let mbm_b be the number of retained upper four-set candidates. Replace each −6z(b,B)-6z(b,B) by 6(1−z(b,B))6(1-z(b,B)) and increase the right-hand side to 840+6mb840+6m_b. This identity reduces the signed inequality to the nonnegative weighted encoding in Proposition S2.1.

Certificate inventory and verification record

Table S2 records the fifteen uniform formulas. Each allows the selected cardinality to vary over the entire interval 35≤N≤4035\leq N\leq40. Every formula has been reconstructed byte for byte, and every refutation has been checked through an empty clause by the separate RUP implementation supplied with this work.

The total number of checked RUP additions is 7,023,863. Two of these refutations, G26 and T1, were additionally checked using a separate Glucose 4 propagation implementation, with 163,776 checked additions in total and no calls to SAT search. This second check concerns these two formulas, not all fifteen.

Independent implementation checks cover the pruning steps, the local orbit partitions, and agreement of the proper-cycle data with the constructions in Section S1. The signed weighted encoding was tested on 6,144 assignments and the integer identities on 402,682 profiles as regression checks. Their mathematical justification is given above and in Section S2. A known eight-rectangle covering at n=34n = 34 is included as a positive control and is accepted when the lower selection threshold is 34. Its rectangles are checked on every matrix position.

The supplement eight-rectangle-threshold-certificate.zip contains the fifteen CNFs and DRUP refutations, the checker and its source, generators, audits, proper-cycle parameters, the positive control, the published upper-bound witnesses, and a SHA-256 manifest. Checking saved refutations does not require a SAT-solver package. Rebuilding formulas uses python-sat==1.9.dev17. The key mathematical lemmas are given in the main paper; the complete parameters and encodings needed to inspect the certificates are given here.

Proof checking and reproduction commands

RUP checking and its scope

Refutations were produced by CaDiCaL 3.0.0 through Python-SAT 1.9.dev17 [3, 2]. A clause LL has the reverse-unit-propagation (RUP) property relative to a formula FF if unit propagation on F∧⋀ℓ∈L¬ℓF \land\bigwedge_{\ell\in L} \neg\ell yields a contradiction. Thus FF entails LL. The supplied C# checker verifies every addition in this sense and accepts only after verifying the empty clause. It uses no SAT-solver library. The deletion-enabled RUP format is a restricted form of DRAT [4]; no unchecked RAT-only step is used.

The checker may retain previously justified root-level consequences when processing deletions. These remain entailed by the original CNF, so retaining them preserves soundness of the refutation. The additional Glucose check likewise retains original and verified unit clauses while processing other deletions in batches.

Refutation checking establishes unsatisfiability of the supplied CNFs. The local-exclusion arguments in the main paper justify their coverage of the original mathematical problem, and Section S1 justifies their proper-cycle clauses. The trusted components include these reductions, the encodings, the checker, and the execution environment. No third-party audit or proof-assistant formalization is asserted.

Verification commands

From the extracted archive root, the published upper witnesses can be checked using only the Python standard library:

python outputs/verify_upper_covers.py outputs/upper-covers-35-55.json

The fifteen refutations can be checked on Windows with the supplied executable:

$cases = ’H43’,’H57’,’H83’,’H99’,’H113’,’G23’,’G25’,’G26’,
         ’T1’,’T2’,’T3’,’M0’,’M2’,’F35’,’F37’
foreach ($name in $cases) {
    & .\work\RupCheck2.exe "work/threshold35/$name.cnf" `
                           "work/threshold35/$name.drup"
    if ($LASTEXITCODE -ne 0) { throw "Rejected: $name" }
}

The checker source is work/RupCheck.cs. With the pinned Python-SAT version installed, the arithmetic audit and the formula-reconstruction audit are

python work/audit_threshold_data.py
python work/audit_threshold_proofs.py

These audits check arithmetic, controls, model reconstruction, hashes, and recorded checker results. They do not replace running the RUP checker on the proof files.

An unfinished search is reported as UNKNOWN and is not a proof. The reported exclusions depend on the saved, checked refutations.

Published size-nine witnesses

For completeness of the supplementary record, we include all twenty-one published size-nine witnesses in upper-covers-35-55.json, together with their source-file hashes and a standard-library checker verify_upper_covers.py. Their source is the supporting data linked from [1]; they are not new constructions of this paper. To decode a witness, let ci,dj∈{0,1}9c_i,d_j \in\{0,1\}^9 be its row and column membership vectors. The nine rectangles are explicitly

Rt={i:(ci)t=1}×{j:(dj)t=1},0≤t≤8.(42)R_t = \{i : (c_i)_t = 1\} \times\{j : (d_j)_t = 1\}, \qquad0 \le t \le8. \tag*{(42)}

The checker verifies the exact integer condition

∑t=08(ci)t(dj)t>0  ⟺  i∉{j,j+1}(modn).(43)\sum_{t=0}^{8}(c_i)_t(d_j)_t > 0 \iff i \notin\{j,j+1\} \pmod{n}. \tag*{(43)}

It therefore checks both the absence of zero entries in the rectangles and the coverage of every positive entry. All 43,295 matrix positions in these twenty-one witnesses pass this check.

References

  1. [1][S1] A. P. Goucha, J. Gouveia, and P. M. Silva, On ranks of regular polygons, arXiv:1610.09868v2, 2016. https://arxiv.org/abs/1610.09868v2. Supporting factorizations: https://www.mat.uc.pt/~jgouveia/polyrank.html.
  2. [2][S2] A. Ignatiev, A. Morgado, and J. Marques-Silva, PySAT: A Python toolkit for prototyping with SAT oracles, in Theory and Applications of Satisfiability Testing—SAT 2018, pp. 428–437, 2018. https://doi.org/10.1007/978-3-319-94144-8_26.
  3. [3][S3] A. Biere and contributors, CaDiCaL SAT Solver, release 3.0.0, software. https://github.com/arminbiere/cadical. Accessed 29 October 2026.
  4. [4][S4] N. Wetzler, M. J. H. Heule, and W. A. Hunt, Jr., DRAT-trim: Efficient checking and trimming using expressive clausal proofs, in Theory and Applications of Satisfiability Testing—SAT 2014, Lecture Notes in Computer Science 8561, pp. 422–429, 2014. Project documentation: https://www.cs.utexas.edu/~marijn/drat-trim/.DOI

Paper details

vlnc:W_shajppbx
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Codex

View statement
Looking for related papers…
Contents