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 be a convex polygon with exactly vertices and irredundant facet inequalities. After cyclically indexing rows and columns, its slack matrix has the support of the zero-one matrix defined by
All other entries are one. Explicitly, the support matrix has the cyclic form
A rectangle of a nonnegative matrix is a set contained in . The rectangle covering number is the smallest number of such rectangles whose union is . It equals the Boolean rank : 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 to mean the Boolean rank of its zero-one support matrix. Thus
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 . In the interval , the asterisk in that table marks an upper bound whose optimality was not established. For , the equality with nine is already established. Engel, Kalinowski, and Schymura [2] also list the bounds for .
Proposition 1.1 (Published upper bound). For every , one has .
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 with vertices,
Corollary 1.3. For every convex polygon with vertices,
Proof. Use Theorem 1.2 for . For , use the exact values already established in [1].
Proof strategy and dependencies
Only the lower bound for 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:
Section 2 turns such a covering into a saturated inclusion cycle on eight coordinates.
Section 3 proves rank restrictions and an exact penalty budget by maximal-chain counting.
Section 4 excludes equality in that budget, giving without a computational refutation.
Section 5 excludes the remaining cycles through the H, G, T, M, and F stages. Section 6 then assembles the argument.
Here denotes the polygon order and the number of lower vertices in an inclusion cycle; the normal form gives . The saved selection formulas allow every simultaneously. Thus the finite exclusions use no assumption of homogeneity or monotonicity in .
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 and use cyclic indices in . 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 .
The maximal-rectangle normal form
Lemma 2.1 (Maximal-rectangle normal form). Suppose has a covering by rectangles: . There is a covering by rectangles with row membership sets and column membership sets . Let , then we have
Proof. For a rectangle , let consist of every column compatible with all rows in , and let consist of every row compatible with all columns in . Then and . A column outside has a zero in some row of , hence also in a row of . Thus is maximal on both sides. Extend every rectangle this way. No previously covered positive position is lost.
For a maximal rectangle indexed by , column belongs to the rectangle exactly when neither row nor row belongs to it. Consequently exactly when , proving (2). Similarly, row belongs to the rectangle exactly when neither column nor column belongs to it. This gives (3).
Finally, position is uncovered exactly when , or equivalently . The prescribed zero positions are precisely those in (4).
Antichains and the induced cycle
Lemma 2.2. For , sets satisfying (4) form two antichains and , each of cardinality . No member of equals a member of . The bipartite graph defined by strict inclusion is an induced alternating cycle of length .
Proof. If , then lies in both and . By (4), belongs to both and , so . This proves the first antichain assertion and also distinctness of the .
If , its two lower neighbors are also lower neighbors of . Equation (4) then implies and hence . If , the other lower neighbor of would be contained in , contrary to the first assertion. The last statement now follows directly from (4).
Conversely, a cyclic sequence satisfying (4), with , yields a covering. Its rectangle indexed by is
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.

Figure 1. (a) Bipartite inclusion graph \quad (b) Alternating cycle. .
Complement duality and homogeneity
Lemma 2.3 (Complement duality). Taking , preserves a saturated inclusion cycle. An inclusion edge has rank type ; under this transformation, rank type becomes .
Proof. Taking complements and exchanging the two families preserves the antichain property. Moreover,
The inclusion condition is also preserved:
Finally, an edge becomes , whose rank type is .
A cycle is homogeneous of type if every lower set has size and every upper set has size .
Maximal-chain counting and the penalty budget
The exact chain identity
A chain in 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
Thus a maximal chain contains exactly one set of each cardinality. It is uniquely determined by a permutation of , through
Choosing the permutation uniformly therefore gives a uniformly random maximal chain.
We say that meets a family if some set on the chain belongs to ; equivalently,
If is an antichain, the chain can contain at most one member of , since any two distinct sets on the chain are comparable by inclusion.
Lemma 3.1 (Chain identity). Let be disjoint antichains in , with every cross-comparability oriented from to . Let be the set of pairs with . A uniformly random maximal chain satisfies
Proof. There are maximal chains. A set of size lies on of them. A nested pair of sizes lies on of them. A chain meets each antichain at most once. If it meets both, the two selected sets form a pair in . 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 for some and , a lower neighbor of would satisfy
contradicting the antichain property of .
Define, for ,
In particular, the eight-coordinate formula is
For an inclusion cycle, every selected vertex has degree two. Therefore Lemma 3.1 becomes
For an induced alternating path with lower vertices and upper vertices, whose endpoints are , the corresponding inequality is
Analytic bounds for the chain weights
Lemma 3.2 (Analytic weight minima). The chain weights satisfy
Equality in (11) holds only at (3, 4); equality in (12) holds only at (3, 4) and (4, 5).
Proof. For , all fifteen admissible pairs are listed below:
| 30 | 32 | 33 | 36 | 50 | |
| – | 12 | 14 | 18 | 36 | |
| – | – | 9 | 14 | 33 | |
| – | – | – | 12 | 32 | |
| – | – | – | – | 30 |
Table 1.
The smallest entry is 9, attained only at (3, 4). Thus the minimum weight is .
For , all ten admissible pairs in the stated range are:
| 35 | 38 | 42 | 56 | |
| – | 21 | 27 | 42 | |
| – | – | 21 | 38 | |
| – | – | – | 35 |
Table 2.
The smallest entry is 21, attained only at (3, 4) and (4, 5). Thus the minimum weight is .
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 . 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 .
Lemma 3.2 gives , while binomial unimodality gives . There are edges, so (10) implies
Hence $m\leq 23.
Proposition 3.4. Every saturated inclusion cycle with lower vertices in satisfies
Proof. We first show that for every . The empty set cannot belong to , since is an antichain with more than one member.
Suppose that . Every other lower set omits , by the antichain property. Delete and its two upper neighbors. Each remaining upper set is the union of two remaining lower sets, so it also omits . The resulting induced alternating path therefore lies on the seven-element ground set and has lower vertices, contradicting Lemma 3.3. Thus for every .
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,
Every lower set has an upper neighbor with . Hence
Finally, every upper set has a lower neighbor with . Using the lower bound already proved gives
Together, these bounds yield
The common penalty budget
For the ranks in (13), define the integer penalty
Lemma 3.2 proves analytically. For example,
Substitution in (8), using , gives the complete exact penalty table
| 14 | 17 | 21 | 35 | 0 | 6 | 21 | 0 | 17 | 14 |
Table 15.
These are rational identities, rather than numerical approximations.
There are inclusion edges. Subtracting their baseline contribution from (9) and multiplying by 1680 gives
This is the common counting budget for .
If counts lower sets of sizes 2, 5, each of its two incident edges has penalty at least 14. The same assertion holds if instead counts upper sets of sizes 3, 6. For either family separately,
The analytic exclusion of order 40
The nonnegative penalties in (16) already give . 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 on seven vertices such that for every nonadjacent pair .
Proof. First, every vertex has degree at most two. Indeed, if a vertex had degree at least three, any nonneighbor would satisfy . Thus 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 were isolated, the condition applied to and any other vertex would give . 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 is connected. Suppose it were disconnected. If one component contained a degree-two vertex , choose a vertex from another component. There are no isolated vertices, so . The neighborhoods of and lie in different components, and hence
a contradiction. Therefore every vertex in a disconnected would have degree one. Such a graph is a disjoint union of edges and cannot have seven vertices. Thus is connected.
A connected graph on seven vertices with maximum degree two is a path or a cycle . 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 there is nothing to prove. Otherwise, the rank bounds and nonnegative penalties in (16) give .
Suppose . The chain budget is then zero. Its zero-penalty edge types are and , so connectedness forces one homogeneous type. After complement duality, assume that the lower family consists of 40 four-sets and the upper family of 40 five-sets.
The chain identity now has value . Every maximal chain must therefore meet . In particular, a four-set outside cannot be contained in a five-set outside : a maximal chain through that pair would meet neither selected family.
Let be the family of triples complementary to the five-sets outside . Let be the family of four-sets complementary to members of . If , its complement is a selected four-set, which has exactly two selected five-set supersets out of its four supersets. Thus contains exactly two members of . If , all four supersets of its complement are selected five-sets, so it contains no member of . Every four-set consequently contains either zero or two members of , and belongs to exactly in the latter case.
Also, every triple is contained in exactly two members of : its complementary five-set belongs to and has exactly two selected lower neighbors. Fix a coordinate and form a graph on the other seven coordinates, with edge when . This graph is triangle-free, since a triangle would give a four-set containing at least three members of .
For a nonedge , the triple is not in . For each remaining coordinate , the four-set belongs to precisely when or is an edge. Indeed, if neither is an edge, its only possible member of is , and the zero-or-two rule forces zero. If at least one is an edge, the same rule forces two.
Since has exactly two extensions in , the graph satisfies
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 . Each selected vertex has degree two, so the two selected cardinalities are equal. Write their common value as . Keeping 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 indicate selection of a set-vertex. If is an induced alternating cycle with fewer than 70 vertices in the strict-inclusion graph, every induced -cycle with satisfies
The same holds for every coordinate-permuted copy of .
Proof. If all vertices of were selected, each would already have two selected neighbors in . The degree-two constraints would preclude any edge to the remaining selected vertices. Thus 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 or , the extreme count in (16) is , giving , impossible here. Together with the rank restrictions, this leaves the homogeneous types and . Complement duality reduces them to .
Lemma 5.3 (Five homogeneous branches). Every homogeneous cycle of type with lower vertices can be relabeled so that its first three lower sets are
Its fourth set is , where the pair can be chosen from
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 distinct lower sets, a contradiction.
Choose a triple whose intersection has size two. Normalize the first two sets to and . 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
The earlier upper set would contain if , so this value is forbidden. For , the new upper union omits coordinate 2 and therefore contains neither nor . The only further obstruction is containment in : it occurs precisely when . Thus the complete condition is
The prefix stabilizer independently swaps 0, 1 and 6, 7. For , it distinguishes deletion of a core element from deletion of 4; deletion of 5 is forbidden. For , 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 , no homogeneous saturated inclusion cycle of type 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.
| Case | Variables | Initial clauses | Checked RUP additions |
| H43 | 5,158 | 38,915 | 316,971 |
| H57 | 5,158 | 38,915 | 325,151 |
| H83 | 5,158 | 38,915 | 430,293 |
| H99 | 5,158 | 38,915 | 206,040 |
| H113 | 5,158 | 38,915 | 285,331 |
| G23 | 42,272 | 104,461 | 339,780 |
| G25 | 46,372 | 115,028 | 501,582 |
| G26 | 43,730 | 105,857 | 132,152 |
| T1 | 13,402 | 33,498 | 31,624 |
| T2 | 18,444 | 47,655 | 270,546 |
| T3 | 18,032 | 46,516 | 254,984 |
| M0 | 27,355 | 69,151 | 778,136 |
| M2 | 26,807 | 71,852 | 523,646 |
| F35 | 26,375 | 70,957 | 1,070,069 |
| F37 | 26,375 | 71,072 | 1,557,558 |
Table S2. Uniform exclusions for .
Complement duality also excludes the homogeneous type .
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 lower vertices has no edge of type , , or .
Proof. For each chosen type , normalize its edge to
The other lower neighbor of satisfies . Thus
with a proper subset of . The lower rank bound and the swap of 0 and 1 give these representatives:
| or | ||
| or |
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 .
Corollary 5.6. Every remaining saturated inclusion cycle has lower ranks in and upper ranks in . Its possible edge types are exactly among
Proof. Complement duality also excludes and . 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 count lower sets of sizes 2, 3, 4, and let count upper sets of sizes 4, 6, respectively. Then . Write for the number of edges. All edges incident with lower two-sets end at upper four-sets. Consequently the number of edges is , and counting at lower three-sets gives
The only nonzero penalties among (23) are 17 on and 6 on Therefore
The last identity uses . It is the constant-right-hand-side weighted constraint used in the uniform formulas. Since and , the first inequality also gives
Stage T: removing lower two-sets and upper six-sets
After , 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 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 , , . Split the upper family into , whose members contain at least one , and , whose members contain none. Each has exactly two upper neighbors, so there are six pair–upper incidences and .
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
The first term uses all three pairs and one remaining coordinate; the second uses two pairs and both remaining coordinates.
Write for the members of of size . Let be the family of four-subsets of members of . Every member of 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
Since the upper family is an antichain, . Therefore
It follows that
:::
Lemma 5.8 (Four local branches). If , complement duality permits . After relabeling, a five-vertex subpath has the form
where
and
Proof. Duality exchanges and , so choose . Then . Fix a two-element lower set . Both upper neighbors have size four, and their intersection is precisely . Their two-element parts outside are therefore disjoint; call them . By the union identity, the other lower neighbor on each side is or , where are empty or singleton subsets of .
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 .
Proof. If , choose complement orientation and apply Lemma 5.8. Branch T contains three pairwise disjoint lower pairs, contradicting Lemma 5.7 because .
For each other branch, fix its five-vertex path and use the remaining rank pairs, the base and proper-cycle clauses, (25), (26), and . 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 mixed. If there were no mixed edge, connectedness would force a homogeneous type or , contrary to Lemma 5.4 and duality. Hence , and
All preceding exclusions are preserved by complement duality. Under this duality, becomes . Choose the orientation
This choice precedes the local normalization, which uses only coordinate permutations. The whole cycle cannot be mixed: would imply , contrary to .
Lemma 5.10 (Three boundary branches). In a cycle satisfying (32), a mixed edge can be chosen and normalized as
Let be the other lower neighbor of and the other upper neighbor of . Write
Then the three possible branches have representatives
| branch | ||
| M | ||
| M | ||
| M |
Table 35.
Proof. By (31), mixed edges do not occupy the entire -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 and . The union identity requires that contain and either one or two elements of . The intersection identity requires that be together with either one or two elements of . The core coordinates and the outside coordinates may be permuted independently.
If and , both adjacent edges are mixed, contrary to the boundary choice. For each remaining pair of sizes, the independent permutations of and 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:
Indeed, and
give the first bounds. Since , the same inequality gives
and gives . Finally, and imply . These consequences are valid before imposing any matching condition.
Lemma 5.11 (Computational lemma M). Neither boundary branch nor 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 , (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 and , giving M0. If the nonmixed neighbor is incident with its upper endpoint, then and , 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
and upper sets
The other lower neighbor of can be chosen as or .
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 of has size three and satisfies . Its possibilities are exactly
The swap fixes , , , , 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 or , 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 and two of its mixed neighbors , this last condition is the clause
The two formulas F35 and F37 have checked RUP refutations. The suffixes are the decimal masks of , not matrix orders.
Completion of the main proof
Proof of Theorem 1.2. Suppose 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 lower vertices. Proposition 3.4 gives its rank ranges, and (15) gives its penalty budget. Proposition 4.2 gives , leaving only .
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 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 . Proposition 1.1 supplies the published upper bound . Since rectangle covering number depends only on the support, the same equality holds for .
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 for the zero–one matrix whose zeros are and modulo . A saturated inclusion cycle consists of two antichains and satisfying
The saved formulas use and allow with . The analytic length bound in the main paper excludes 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 indicate selection of a set-vertex. If is an induced alternating cycle with fewer than 70 vertices in the strict-inclusion graph, every induced -cycle with satisfies
The same holds for every coordinate-permuted copy of .
Proof. If all vertices of were selected, each would already have two selected neighbors in . The degree-two constraints would preclude any edge to the remaining selected vertices. Thus 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 be distinct coordinates, let be disjoint from them, and let . With indices modulo , define
Then is a saturated inclusion cycle. Denote this construction by .
Proof. The union and intersection identities follow from consecutive intervals and . To check inclusion, fix and regard as a proper arc of the cyclic order. A consecutive -element interval contained in this arc can start only at or . A later start would meet , which is outside the arc; a start outside the arc is immediately excluded. Hence exactly when or .
Lemma S1.3 (Subdivision using fresh coordinates). Suppose consecutive lower sets in a saturated inclusion cycle are and , with outside . For fresh coordinates absent from every old set, replace this adjacency by the lower-set path
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 . An old lower set contained in it would consequently lie in , , or . 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.
The H representatives
For the only subdivision pattern needed here, take eight distinct coordinates in the order , put , and use the cyclic sequence
Call it . Start with and subdivide the adjacency between and using the fresh coordinates . Lemma S1.3 proves (S1.2).
Table S1 gives exact construction parameters for all seventeen H representatives. In an row the third column is and the fourth is the ordered cyclic list of coordinates. In an row the fourth column is . 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.
| ID | Construction | Core | Ordered coordinates |
| H43.1 | 0, 4, 1, 6, 7 | ||
| H43.2 | – | 6, 4, 3, 7, 1, 2, 5, 0 | |
| H43.3 | 0, 4, 7, 3, 6 | ||
| H57.1 | – | 0, 1, 3, 7, 4, 2, 5, 6 | |
| H57.2 | 0, 4, 2, 3, 1, 6, 5 | ||
| H57.3 | 1, 2, 3, 5, 4 | ||
| H57.4 | 0, 5, 1, 3, 7 | ||
| H83.1 | 0, 6, 5, 3, 7 | ||
| H83.2 | 2, 5, 3, 4, 6 | ||
| H83.3 | – | 0, 5, 6, 7, 3, 2, 4, 1 | |
| H99.1 | 2, 5, 3, 4, 6 | ||
| H99.2 | 0, 3, 2, 5, 6, 1, 4 | ||
| H99.3 | 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.
| ID | Construction | Core | Ordered coordinates |
| H113.1 | — | 7, 2, 5, 6, 0, 3, 4, 1 | |
| H113.2 | 0, 2, 6, 4, 3 | ||
| H113.3 | 1, 6, 2, 5, 3, 4, 7 | ||
| H113.4 | 1, 2, 6, 5, 7 |
Table 3.
The Q representatives
Lemma S1.4 (Disjoint petals). Let be nonempty pairwise disjoint sets, disjoint from a core . The lower sets and upper sets , with indices modulo , form a saturated six-vertex inclusion cycle.
Proof. Disjointness and nonemptiness give exactly when . Taking the indicated unions and intersections recovers and respectively.
The four Q representatives follow immediately from these petals:
Table 4.
Their lower-mask sequences are respectively , , , and . 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 . 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, , , count selected lower sets of sizes 2, 3, 4, and , count selected upper sets of sizes 4, 6. After the G exclusions, . The main paper proves the following constraints, which we restate to specify the encodings without external equation references:
Here counts lower sets of sizes 2, 5 or, separately, upper sets of sizes 3, 6. After the G exclusions, the weighted constraint is
After the T exclusions, the M and F stages have and use the dual orientation , equivalently , as well as
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 by the decimal mask . This explains the numerical suffixes of the formula names. For each retained lower or upper candidate introduce a selection variable or . The base clauses impose the following conditions:
Select between 35 and 40 sets in each family.
Do not select two distinct comparable sets in either family, or the same set in both families.
Every selected vertex has exactly two selected permitted strict-inclusion neighbors. For a previously excluded rank pair, prohibit selection of both endpoints.
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
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 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), , and . The M and F formulas use (S2.2) with , , 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 .
Proof. A half-adder satisfies , where and . A full-adder satisfies
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 in binary and place its input literal 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 equals .
Pad and with leading zeroes to a common length. For every position with , use the clause
It forbids when all more significant bits match . If , the highest differing bit violates exactly such a clause. If , every such clause is satisfied, either at position or by a higher differing bit. Thus these clauses express . The gate equations determine their auxiliary values from the inputs, proving existential equivalence.
In (S2.2), let be the number of retained upper four-set candidates. Replace each by and increase the right-hand side to . 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 . 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 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 has the reverse-unit-propagation (RUP) property relative to a formula if unit propagation on yields a contradiction. Thus entails . 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 be its row and column membership vectors. The nine rectangles are explicitly
The checker verifies the exact integer condition
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][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][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][S3] A. Biere and contributors, CaDiCaL SAT Solver, release 3.0.0, software. https://github.com/arminbiere/cadical. Accessed 29 October 2026.
- [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