WorksMathematics
On : the Hole Extensions of the Chen–Chen Configuration Are Reducible, and the Extremal Configurations of Are Not Unique
Abstract
The second order extended Zarankiewicz number of Qi and Yu allows a secondary half of a -edge to be shared, while the -edge graph stays -free and extremal and -edges and main halves stay exclusive. Whether is open. Since deleting a -edge removes exactly one displayed square, if and only if there is no irreducible admissible configuration with exactly displayed squares, and by the cell count of Qi and Yu and the heredity of irreducibility such a configuration without empty cells is an extremal -square configuration of plus one -edge at its hole. For the extremal configuration of Chen and Chen we show, by certificates verified in exact rational arithmetic, that all such extensions have SOS rank at most : by product relations and by contraction certificates of Xu–Yan type. We also show, with computer-assisted certificates and an exhaustive isomorphism search, that the extremal configurations of fall into at least six isomorphism classes; Chen and Chen leave the structural classification of extremal augmented graphs open. Finally we prove a six-to-four reduction. For irreducible configurations whose -edge graph is -free with edges it bounds the multiplicity of a shared half by ( at ), and it applies directly to an explicit number of the extensions of any extremal configuration of , eight for that of Chen and Chen, bringing each to at most squares, in agreement with the certificates. The cell count, the heredity lemma, the rows lemma, the six-to-four identity and a example are checked in Isabelle/HOL; the remaining arguments are written proofs.
Introduction
For an oriented augmented grid on cells, with a set of 1-edges (cells) and a set of 2-edges (pairs of cells, each with a main half and a secondary half), let
We write for the least number of squares of real bilinear forms whose sum is , and call the display of irreducible when , the number of displayed squares. is the largest value of over all biquadratic forms that are sums of squares. In the definition of [7 Definitions 2–3] the 1-edge graph is -free with edges; the 1-edge cells, the main halves and the distinct secondary halves form pairwise disjoint sets; 1-edge cells and main halves are exclusive, while a secondary half may be shared by several 2-edges (condition ). Without sharing this is condition of the second order Zarankiewicz number [4]. denotes the number of empty cells.
Qi and Yu [7] ask whether . The known bounds are . The lower bound comes from the extremal configuration of of Chen and Chen [1], which satisfies and hence ; the upper bound is together with [5 Corollary 7].
Table 1 separates what is proved here from what we use.
| statement | status |
| heredity of irreducibility under deletion of displayed squares | known [4 Lemma 4.17], [8 Lemma 2.11] |
| iff no irreducible 56-square configuration (Prop. 2) | correction of [7 Remark 10], where a deletion lowers by two |
| cell count , and when , | known [7 Remark 10]; cf. [8 eq. (2)] |
| irreducible 55-square cores of an irreducible 56-square configuration with (Prop. 3) | from the count and heredity; proved here |
| rows of an extremal -free graph (Lemma 6) | classical; [1 Lemma 4.1], [8 Lemma 4.6] |
| the 56 extensions of the Chen–Chen base have SOS (Thm. 4) | new (computation); methods from [4, 8] |
| product-relation shortening | known [4 Lemma B.2], [8 Lemma 2.13] |
| contraction criterion | known [8 Lemma 2.15] |
| closure rules for irreducibility | known [4, Definitions 4.1, 4.5; Theorem 4.3, Proposition 4.6], [3 §2] |
| at least six isomorphism classes of extremal configurations | new; classification open in [1 §5.2] |
| six-to-four reduction for a shared half and multiplicity (Lemma 7, Cor. 8) | new application of the product-relation mechanism, and its density consequence |
| exactly extensions admit a direct application of Lemma 7, each with SOS (Prop. 10) | new |
| two cores with unique PSD Gram matrices whose fully occupied union is irreducible (Remark 11) | new example; shared-half examples without extremal 1-edge graph in [7 Remark 6] |
| column bound | projection argument of [5 Corollary 7], [6 Theorem 9], after [2 Corollary 2.15] |
Table 1. Results of this note and the known tools they rest on.
The 56-square reduction
Lemma 1 ([4 Lemma 4.17], [8 Lemma 2.11]). If and , then .
Indeed, a representation of with fewer than squares gives one of with fewer than .
Proposition 2. if and only if there is no irreducible -admissible configuration at whose 1-edge graph is -free with 27 edges and which has exactly 56 displayed squares.
Proof. Delete a 2-edge of an irreducible admissible configuration with squares, keeping the orientation of every remaining edge. This removes one complete square, leaves unchanged and keeps ; by Lemma 1 the result is irreducible with squares. Repeating, an irreducible admissible configuration of any length yields one of length 56. Since an irreducible admissible 55-square configuration exists [1], the statement follows. This corrects the deletion count in [7 Remark 10]: a 2-edge contributes one displayed square, so there is no separate case .
The same descent to the next size is used for in [4 proof of Corollary 4.19] and [8 proof of Theorem 4.4]. The cell count below is [7 Remark 10] (compare [8 eq. (2)] for ); we include its short proof because the rest of the note depends on it.
Proposition 3. Let be admissible at with , two-edges, distinct secondary halves, and . Then
and if and , then [7 Remark 10]. If moreover is irreducible, deleting either of the two 2-edges at the shared secondary half leaves an irreducible configuration satisfying with 55 squares and one hole, that is, an extremal configuration of .
Proof. The 1-edge cells, the main halves and the distinct secondary halves are pairwise disjoint, of sizes 27, and , so . Substituting and gives the identity. At , it reads : exactly one secondary cell is used by two 2-edges and every other by one. Deleting either of these two edges makes its exclusive main half the unique hole; every remaining secondary cell has multiplicity one, so (S) holds, and irreducibility follows from Lemma 1.
So every irreducible admissible 56-square configuration with is an extremal 55-square configuration plus one 2-edge joining its hole to a half of one of its 2-edges. For one has , and deleting one 2-edge can leave sharing.
The 56 extensions of the Chen–Chen base
Let be the 21-row configuration obtained in [1 §4.2] by the deletion of [1 Proposition 4.10], with rows renumbered consecutively. It has 27 one-edges, 28 two-edges and the unique hole . For each half of an odd 2-edge, orient that edge with secondary half and adjoin the 2-edge with main half and secondary half . This gives an -admissible display with 56 squares and ; orientation does not change , and since a 1-edge cell cannot be shared these 56 displays are all the extensions of by one 2-edge at .
Theorem 4. For each of the 56 extensions, .
Proof. Write for the displayed forms and for the vector of the 84 cell monomials, .
Product relations, 32 extensions. The certificate gives rational numbers , not all zero, with
identically. By the product-relation lemma [4 Lemma B.2] (see also [8 Lemma 2.13]), is a sum of at most 55 squares: with the symmetric matrix , , , and , the matrix is positive semidefinite, singular, and represents in the displayed basis.
Contraction certificates, 24 extensions, among them . Here the 1596 products , , are linearly independent. Let be the span of the rows of ; each displayed form has an exclusive cell, so has rank 56, and a Gram matrix with range in has the form . Product independence forces . Hence the displayed Gram matrix is an extreme point of the Gram spectrahedron of and the only feasible Gram matrix with range in , so a representation with fewer than 56 squares uses at least one form outside the displayed span (compare [8 Proposition 5.4]). The certificate [8 Lemma 2.15] specifies a rational affine family
and a rational matrix of full column rank with for every : the checker verifies the identity at and that every direction has zero polynomial image. After the recorded permutation,
with of order 55. The exact bounds of [8 Lemma 2.15] prove on the box and a zero of the Schur complement in that box. Then is positive semidefinite of rank exactly 55, and .
Table 2 lists the certificate of each extension and Figure 1 shows where the two kinds lie on the grid. The type depends only on the old 2-edge: both halves of an old edge give the same kind of certificate (16 edges by product relations, 12 by contraction).

Figure 1. The base on the grid. Grey tiles: 1-edges. Each 2-edge is an arc between its two cells, solid blue if both of its extensions are reduced by a product relation and dashed orange if both are reduced by a contraction certificate. The black dashed arc is the extension from the hole to . The complete pairings are in chen_chen_base55.json of the supplement, and the plotting script is included.
Remark 5 (Scope of the certificates). All acceptance checks use exact rational arithmetic implemented with arbitrary-precision integers; the verifier rebuilds each target polynomial from the base and rejects three deliberately altered certificates. The rank-55 Gram matrix of item (ii) is proved to exist; its entries are not asserted to be rational, and it is not written down. The certificates give upper bounds only, for the 56 extensions of and for configurations obtained from them by relabelling rows and columns. They do not give the minimum number of squares. Apart from one extension of each configuration of § 4 (since ), they say nothing about extensions of other extremal configurations.
| 2-edge | certificate | ||||
| contraction | 76 | 0.235 | |||
| contraction | 76 | 0.040 | |||
| product relation (15 products) | |||||
| product relation (13 products) | |||||
| product relation (4 products) | |||||
| product relation (3 products) | |||||
| product relation (3 products) | |||||
| product relation (4 products) | |||||
| product relation (4 products) | |||||
| 2-edge | certificate | ||||
| product relation (3 products) | |||||
| product relation (4 products) | |||||
| product relation (3 products) | |||||
| contraction | 75 | 0.053 | |||
| contraction | 75 | 0.277 | |||
| product relation (4 products) | |||||
| product relation (3 products) | |||||
| product relation (6 products) | |||||
| product relation (7 products) | |||||
| product relation (4 products) | |||||
| product relation (5 products) | |||||
| product relation (10 products) | |||||
| product relation (11 products) | |||||
| contraction | 77 | 0.009 | |||
| contraction | 77 | 0.061 | |||
| contraction | 77 | 0.049 | |||
| contraction | 77 | 0.103 | |||
| product relation (3 products) | |||||
| product relation (4 products) | |||||
| product relation (10 products) | |||||
| product relation (10 products) | |||||
| product relation (11 products) | |||||
| product relation (2 products) | |||||
| product relation (3 products) | |||||
| product relation (4 products) | |||||
| product relation (3 products) | |||||
| product relation (4 products) | |||||
| product relation (9 products) | |||||
| product relation (10 products) | |||||
| contraction | 75 | 0.020 | |||
| contraction | 75 | 0.026 | |||
| contraction | 76 | 0.207 | |||
| contraction | 76 | 0.090 | |||
| contraction | 75 | 0.018 | |||
| contraction | 75 | 0.046 | |||
| contraction | 75 | 0.027 | |||
| contraction | 75 | 0.039 | |||
| contraction | 76 | 0.106 | |||
| contraction | 76 | 0.118 | |||
| contraction | 75 | 0.028 | |||
| contraction | 75 | 0.053 | |||
| product relation (10 products) | |||||
| product relation (9 products) | |||||
| contraction | 76 | 0.183 | |||
| contraction | 76 | 0.066 |
Table 2. The 56 extensions , , grouped by the old 2-edge of the base. For a product relation: the number of products in the certified relation. For a contraction: the order of the reduced Gram block , the contraction constant and the bound checked against . Decimal entries are rounded for display; the acceptance comparisons use the exact rational values in the supplementary data.
| 2-edge | certificate | ||||
| contraction | 75 | 0.027 | |||
| contraction | 75 | 0.049 |
Table 2 (PDF p. 7). Table 2, continued
Other extremal configurations
Replacing an old 2-edge of by gives a 55-square configuration with its hole at . Of the 56 configurations , sixteen have a product relation among their displayed forms, hence are reducible; the closure below decides six as irreducible; the other 34 are undecided. For the six choices of in Table 3, the closure rules of [4 Definitions 4.1 and 4.5] and [3 §2], sound by [4 Theorem 4.3, Proposition 4.6] (coefficient identities on rectangles, the empty cell, Cauchy–Schwarz saturation and substitution of equal vectors) fix all products among the 83 occupied cell vectors, diagonal included, in every positive semidefinite Gram matrix (the products with the empty cell vanish), and the resulting Gram matrix has rank 55. So each of the six is irreducible, hence extremal for . Each certificate is accepted by a separate checker that does not import the generating program.
The configuration with is with rows 9 and 10 exchanged. The other five are pairwise non-isomorphic and not isomorphic to (exhaustive search over the 24 column permutations and all row bijections). A short invariant already separates one of them: has two 2-edges with both halves in one row, and , while the configuration with has only one. Hence the extremal configurations of fall into at least six isomorphism classes, and the case is a question about all of them.
Structural tools
Rows of an extremal 1-edge graph
Lemma 6 ([1 Lemma 4.1], [8 Lemma 4.6]). Let be -free with . Then every row has degree 1 or 2, and every pair of columns lies in exactly one row. In particular this holds for every 1-edge graph of , where .
Proof. Let be the degree of row . Since is -free, distinct rows contain distinct pairs of columns, so . With for every ,
Equality throughout gives , that is , and , so the pairs of columns in the rows are all of them, each once.
This is the classical equality case of the counting behind ; we include the proof because it is short and checked in Isabelle (§ 7).
The six-to-four reduction
Lemma 7. Suppose an -admissible display of length contains the 2-edges and with the same secondary monomial and , and, for some column and row , the 1-edges , , , . Then .
Proof. Put and . Then and , so , and
Replace the six summands by the four on the right and keep the others.
Corollary 8. Let be an irreducible -admissible configuration on cells whose 1-edge graph is -free with . Then a shared secondary half has at most main halves in any one column, hence multiplicity at most . At , with , the multiplicity is at most 12.
Proof. Fix a column and the rows of the main halves in of the 2-edges at one secondary half. The 1-edges of row avoid column , which holds a main half, and by Lemma 6 each row has one or two 1-edges. If rows had 1-edges in a common column , then by Lemma 6 the pair lies in a row with 1-edges at and ; because and are main halves, and Lemma 7 would reduce the display. So the column sets of 1-edges of these rows are nonempty and pairwise disjoint subsets of the other columns.
Remark 9. The transposed form of Lemma 7, with two main halves , in one row, needs a row with 1-edges at , and for a third column . Under the hypothesis of Corollary 8 every row has at most two 1-edges (Lemma 6), so the transposed form never applies there.
Proposition 10. Let be an extremal 55-square configuration of with its unique hole , and let be the set of columns of the 1-edges of row . Among the 56 extensions of by one 2-edge at , exactly
admit a direct application of Lemma 7 to the displayed representation, where is the number of 1-edges in column . Each of these extensions has SOS rank at most 54.
Proof. Since satisfies , the only shared cell in the extension is , common to the new 2-edge and the old one ; condition forces to be secondary in both, with main halves and . The extension keeps , so its rows still have at most two 1-edges, and by Remark 9 Lemma 7 applies only when lies in column and rows and have 1-edges in a common column ; then the row of the pair (Lemma 6) supplies and , and since is the hole and a half. Conversely, let have a 1-edge in some and for all . Then is not a 1-edge (otherwise would contain the pair ), and not a hole, so it is a half , and its extension is reduced. Each such row gives one extension. The rows with a 1-edge in some number , since a row with two columns of is the row of that pair; removing and the distinct rows leaves . Lemma 7 replaces six of the 56 displayed squares by four, so each counted extension has at most 54 squares; this is an upper bound, not the minimum.
For , and , so Lemma 7 reduces 8 extensions by hand: , all with and . This agrees with Table 2: all eight are certified there by product relations with four products each, the shape of the relation of Lemma 7. The six configurations of Table 3 share the 1-edge graph of , and in each of them the row of the new hole again has , so the count is in every case.
| kept half | new hole | products fixed among occupied cells | class |
| all | 1 | ||
| all | 0 | ||
| all | 2 | ||
| all | 3 | ||
| all | 4 | ||
| all | 5 |
Table 3. The six irreducible 55-square configurations obtained from the base by replacing the old 2-edge by . Class: isomorphism class under row and column permutations (0 is the class of the base).
The column bound
For an SOS biquadratic form write . Then
This is the rank-sensitive form, for a single column, of the coefficient-vector projection argument used in [5 proof of Corollary 7] and [6 proof of Theorem 9]; the earlier dimension-only bound is a case of the parallel-line covering bound of [2 Corollary 2.15]. In an SOS representation , the vectors , , span a space of dimension , and the orthogonal projection onto it and onto its complement splits into a sum of at most squares and an SOS form free of . If is an empty cell, in every representation (its squared norm is the zero coefficient of ), so and, with [5 Theorem 1], . This does not exclude an irreducible 56-square display, since ; and for it gives only .
Remark 11 (A example). Let , , , . The forms and each have a unique positive semidefinite Gram matrix (the zero diagonal entry of the empty cell fixes the only free parameter), and their union , with every cell occupied, is not a sum of two squares: its matrix in has determinant , which is not the square of a quadratic form. So full occupancy and two cores with unique Gram matrices do not force reducibility of their union; a proof for the class must use further hypotheses, the extremal density of the 1-edge graph being one possible source. Irreducible configurations with a shared half but with an empty 1-edge graph are given in [7 Remark 6].
Numerical evidence outside Theorem 4
We also examined two 56-square configurations with one empty cell, with the main halves of each shared star in one column. The first has ; the second has and lies in the relaxed class with fewer than 27 one-edges. Our recorded floating-point searches report approximate 55-square decompositions, with coefficient residuals about and . The supplementary files keep summary records only, not the complete targets or computed factors needed to reproduce these residuals. These observations are numerical evidence, not certified upper bounds, and are not used in Theorem 4.
Formal verification
The Isabelle/HOL session Z2M_Hole_Extensions, folder Isabelle/Z2MHoleExtensions of https://github.com/karlesmarin/formalizations, commit 390bf7d (a self-contained copy is in the supplement), formalizes the elementary statements listed below (built without sorry and without quick_and_dirty; a copy with a false lemma appended fails, as it should; the supplement copy is the session MQY_Pieces, with its build log). The heredity theorem is stated for arbitrary families of real-valued functions. The passage from admissible configurations to the premises of the counting and heredity lemmas, the graph-theoretic application of the six-to-four identity, Proposition 2, the core statement of Proposition 3, Corollary 8, Remark 9, Proposition 10, the column bound and the Gram uniqueness in Remark 11 remain in the written proofs.
| statement | Isabelle theorem |
| cell identity of Proposition 3 | display_cell_count, cell_count_21x4 |
| , gives | no_hole_one_share |
| heredity, Lemma 1 | irreducible_delete_square |
| Lemma 6 and the case | c4_free_extremal_rows, every_column_pair_once_21x4 |
| the identity of Lemma 7 | six_to_four |
| the example (not two squares; three) | ex22_not_two_squares, ex22_three_squares |
Table 4.
The certificates of Theorem 4 and Table 3 are checked by the exact verifiers of the supplementary data, not in Isabelle.
Data and reproducibility
The supplementary data contain the base , the 56 extensions, the 32 product-relation certificates, the 24 contraction certificates, the six closure certificates of Table 3, the exact verification programs, the Isabelle session, and a README with the commands, the expected acceptance counts and the checksums of all files. The verification programs use only the Python standard library.
What remains open
Theorem 4 rules out the 56 extensions of without empty cells. By Proposition 3, an irreducible admissible 56-square configuration with is obtained by adjoining one 2-edge to an extremal 55-square configuration, and neither of its two cores is isomorphic to . Excluding all of them requires a result for the other extremal configurations, of which there are at least five more classes. For deleting a 2-edge can leave sharing, and those cases remain open.
Acknowledgment
The first author used an AI assistant during the computational exploration and drafting. The exact certificates are checked by the verification programs of the supplementary data.
References
- [1]Z. Chen, Y. Chen, Recursive-Line Zarankiewicz Numbers with Four Columns, arXiv:2609.11093v2, 2026.arxiv.org/abs/2609.11093
- [2]G. Blekherman, R. Sinn, G. G. Smith, M. Velasco, Sums of squares and quadratic persistence on real projective varieties, J. Eur. Math. Soc. 24 (2022), 925–965; statement numbers as in arXiv:1902.02754v2.DOI
- [3]N. Lebedev, Asymptotic equivalence and exact values for second-order Zarankiewicz numbers, arXiv:2610.05442v1, 2026.arxiv.org/abs/2610.05442
- [4]J. Löfberg, L. Qi, Second Order Zarankiewicz Number, arXiv:2608.30555v3, 2026.arxiv.org/abs/2608.30555
- [5]C. Marín, For m ≥ 2, every m × 3 biquadratic sum of squares is a sum of 2m squares, version 2, Zenodo, 2026, doi:10.5281/zenodo.24051362.
- [6]C. Marín, Quadratic persistence of Segre varieties and a linear gap between biquadratic SOS rank and Zarankiewicz bounds, Zenodo, 2026, doi:10.5281/zenodo.24036320.
- [7]L. Qi, G. Yu, A Second Order Extended Zarankiewicz Number for Biquadratic SOS Rank, version 6, Zenodo, 2026, doi:10.5281/zenodo.24156935.arxiv.org/abs/2611.13858
- [8]Y. Xu, X. Yan, Exact Values, Extremal Classifications, and Sum-of-Squares Reductions for Second-Order Zarankiewicz Numbers, arXiv:2609.18429v1, 2026.arxiv.org/abs/2609.18429