betaFeedback

WorksMathematics

On z2M(21,4)z_{2M}(21,4): the Hole Extensions of the Chen–Chen Configuration Are Reducible, and the Extremal Configurations of z2(21,4)z_2(21,4) Are Not Unique

Abstract

The second order extended Zarankiewicz number z2M(m,n)z_{2M}(m,n) of Qi and Yu allows a secondary half of a 22-edge to be shared, while the 11-edge graph stays C4C_4-free and extremal and 11-edges and main halves stay exclusive. Whether z2M(21,4)=55z_{2M}(21,4)=55 is open. Since deleting a 22-edge removes exactly one displayed square, z2M(21,4)=55z_{2M}(21,4)=55 if and only if there is no irreducible admissible configuration with exactly 5656 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 5555-square configuration of z2(21,4)z_2(21,4) plus one 22-edge at its hole. For the extremal configuration of Chen and Chen we show, by certificates verified in exact rational arithmetic, that all 5656 such extensions have SOS rank at most 5555: 3232 by product relations and 2424 by contraction certificates of Xu–Yan type. We also show, with computer-assisted certificates and an exhaustive isomorphism search, that the extremal configurations of z2(21,4)z_2(21,4) 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 11-edge graph is C4C_4-free with m+(n2)m+\binom n2 edges it bounds the multiplicity of a shared half by n(n−1)n(n-1) (1212 at 21×421\times4), and it applies directly to an explicit number of the extensions of any extremal configuration of z2(21,4)z_2(21,4), eight for that of Chen and Chen, bringing each to at most 5454 squares, in agreement with the certificates. The cell count, the heredity lemma, the rows lemma, the six-to-four identity and a 2×22\times2 example are checked in Isabelle/HOL; the remaining arguments are written proofs.

Introduction

For an oriented augmented grid GG on m×nm \times n cells, with a set E1E_1 of 1-edges (cells) and a set E2E_2 of 2-edges (pairs of cells, each with a main half and a secondary half), let

PG=∑(i,j)∈E1(xiyj)2+∑{(i,j),(k,ℓ)}∈E2(xiyj+xkyℓ)2P_G = \sum_{(i,j)\in E_1}(x_i y_j)^2 + \sum_{\{(i,j),(k,\ell)\}\in E_2}(x_i y_j+x_k y_\ell)^2

We write SOS⁡(P)\operatorname{SOS}(P) for the least number of squares of real bilinear forms whose sum is PP, and call the display of GG irreducible when SOS⁡(PG)=∣E1∣+∣E2∣\operatorname{SOS}(P_G)=|E_1|+|E_2|, the number tt of displayed squares. BSR⁡(m,n)\operatorname{BSR}(m,n) is the largest value of SOS⁡(P)\operatorname{SOS}(P) over all m×nm \times n biquadratic forms that are sums of squares. In the definition of z2M(m,n)z_{2M}(m,n) [7 Definitions 2–3] the 1-edge graph is C4C_4-free with z(m,n)z(m,n) 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 (SM)(S_M)). Without sharing this is condition (S)(S) of the second order Zarankiewicz number z2z_2 [4]. HH denotes the number of empty cells.

Qi and Yu [7] ask whether z2M(21,4)=55z_{2M}(21,4)=55. The known bounds are 55≤z2M(21,4)≤6355 \le z_{2M}(21,4) \le63. The lower bound comes from the extremal configuration of z2(21,4)=55z_2(21,4)=55 of Chen and Chen [1], which satisfies (S)(S) and hence (SM)(S_M); the upper bound is z2M≤BSR⁡z_{2M} \le\operatorname{BSR} together with BSR⁡(21,4)≤63\operatorname{BSR}(21,4) \le63 [5 Corollary 7].

Table 1 separates what is proved here from what we use.

statementstatus
heredity of irreducibility under deletion of displayed squaresknown [4 Lemma 4.17], [8 Lemma 2.11]
z2M(21,4)=55z_{2M}(21,4)=55 iff no irreducible 56-square configuration (Prop. 2)correction of [7 Remark 10], where a deletion lowers tt by two
cell count 2(t−55)=1+k−H2(t-55)=1+k-H, and k=1k=1 when t=56t=56, H=0H=0known [7 Remark 10]; cf. [8 eq. (2)]
irreducible 55-square cores of an irreducible 56-square configuration with H=0H=0 (Prop. 3)from the count and heredity; proved here
rows of an extremal C4C_4-free graph (Lemma 6)classical; [1 Lemma 4.1], [8 Lemma 4.6]
the 56 extensions of the Chen–Chen base have SOS ≤55\le55 (Thm. 4)new (computation); methods from [4, 8]
product-relation shorteningknown [4 Lemma B.2], [8 Lemma 2.13]
contraction criterionknown [8 Lemma 2.15]
closure rules for irreducibilityknown [4, Definitions 4.1, 4.5; Theorem 4.3, Proposition 4.6], [3 §2]
at least six isomorphism classes of extremal configurationsnew; classification open in [1 §5.2]
six-to-four reduction for a shared half and multiplicity ≤n(n−1)\le n(n-1) (Lemma 7, Cor. 8)new application of the product-relation mechanism, and its density consequence
exactly ∑b∈S0(deg⁡b−2)\sum_{b\in S_0}(\deg b-2) extensions admit a direct application of Lemma 7, each with SOS ≤54\le54 (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 boundprojection 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 P=Q+f2P=Q+f^2 and SOS⁡(P)=t\operatorname{SOS}(P)=t, then SOS⁡(Q)≥t−1\operatorname{SOS}(Q)\ge t-1.

Indeed, a representation of QQ with fewer than t−1t-1 squares gives one of PP with fewer than tt.

Proposition 2. z2M(21,4)=55z_{2M}(21,4)=55 if and only if there is no irreducible (SM)(S_M)-admissible configuration at 21×421 \times4 whose 1-edge graph is C4C_4-free with 27 edges and which has exactly 56 displayed squares.

Proof. Delete a 2-edge of an irreducible admissible configuration with t≥57t \ge57 squares, keeping the orientation of every remaining edge. This removes one complete square, leaves E1E_1 unchanged and keeps (SM)(S_M); by Lemma 1 the result is irreducible with t−1t-1 squares. Repeating, an irreducible admissible configuration of any length t≥56t \ge56 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 t=57t=57.

The same descent to the next size is used for z2z_2 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 z2z_2); we include its short proof because the rest of the note depends on it.

Proposition 3. Let GG be admissible at 21×421 \times4 with ∣E1∣=27|E_1|=27, e2=∣E2∣e_2=|E_2| two-edges, ss distinct secondary halves, k=e2−sk=e_2-s and t=27+e2t=27+e_2. Then

2(t−55)=1+k−H,2(t-55)=1+k-H,

and if t=56t=56 and H=0H=0, then k=1k=1 [7 Remark 10]. If moreover GG is irreducible, deleting either of the two 2-edges at the shared secondary half leaves an irreducible configuration satisfying (S)(S) with 55 squares and one hole, that is, an extremal configuration of z2(21,4)=55z_2(21,4)=55.

Proof. The 1-edge cells, the main halves and the distinct secondary halves are pairwise disjoint, of sizes 27, e2e_2 and ss, so 84=27+e2+s+H84=27+e_2+s+H. Substituting s=e2−ks=e_2-k and e2=t−27e_2=t-27 gives the identity. At t=56t=56, H=0H=0 it reads k=1k=1: 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 H=0H=0 is an extremal 55-square configuration plus one 2-edge joining its hole to a half of one of its 2-edges. For H≥1H\ge1 one has k=H+1≥2k=H+1\ge2, and deleting one 2-edge can leave sharing.

The 56 extensions of the Chen–Chen base

Let G0G_0 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 p=(10,1)p=(10,1). For each half cc of an odd 2-edge, orient that edge with secondary half cc and adjoin the 2-edge with main half pp and secondary half cc. This gives an (SM)(S_M)-admissible display with 56 squares and H=0H=0; orientation does not change PG0P_{G_0}, and since a 1-edge cell cannot be shared these 56 displays are all the extensions of G0G_0 by one 2-edge at pp.

Theorem 4. For each of the 56 extensions, SOS⁡(PG)≤55\operatorname{SOS}(P_G) \le55.

Proof. Write f1,…,f56f_1,\ldots,f_{56} for the displayed forms and zz for the vector of the 84 cell monomials, f=Czf=Cz.

  1. Product relations, 32 extensions. The certificate gives rational numbers crsc_{rs}, not all zero, with

∑1≤r<s≤56crsfrfs=0\sum_{1\le r<s\le56}c_{rs}f_rf_s=0

identically. By the product-relation lemma [4 Lemma B.2] (see also [8 Lemma 2.13]), PGP_G is a sum of at most 55 squares: with the symmetric matrix KK, Krs=Ksr=crs/2K_{rs}=K_{sr}=c_{rs}/2, Krr=0K_{rr}=0, and λ=λmax⁡(K)>0\lambda=\lambda_{\max}(K)>0, the matrix I−K/λI-K/\lambda is positive semidefinite, singular, and represents PGP_G in the displayed basis.

  1. Contraction certificates, 24 extensions, among them c=(17,3)\mathbf{c=(17,3)}. Here the 1596 products frfsf_rf_s, 1≤r≤s≤561\le r\le s\le56, are linearly independent. Let WW be the span of the rows of CC; each displayed form has an exclusive cell, so CC has rank 56, and a Gram matrix with range in WW has the form CTACC^TAC. Product independence forces A=IA=I. Hence the displayed Gram matrix is an extreme point of the Gram spectrahedron of PGP_G and the only feasible Gram matrix with range in WW, 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

Q(h)=Q0+∑jhjBjQ(h)=Q_0+\sum_j h_jB_j

and a rational matrix LL of full column rank with zTLQ(h)LTz≡PGz^TLQ(h)L^Tz\equiv P_G for every hh: the checker verifies the identity at h=0h=0 and that every direction BjB_j has zero polynomial image. After the recorded permutation,

Q(h)=(A(h)D(h)D(h)TE(h)).Q(h)= \begin{pmatrix} A(h) & D(h)\\ D(h)^T & E(h) \end{pmatrix}.

with A(h)A(h) of order 55. The exact bounds of [8 Lemma 2.15] prove A(h)≻0A(h)\succ0 on the box ∥h∥∞≤ε=10−10\lVert h\rVert_\infty\le\varepsilon=10^{-10} and a zero h∗h_* of the Schur complement E−DTA−1DE-D^TA^{-1}D in that box. Then LQ(h∗)LTLQ(h_*)L^T is positive semidefinite of rank exactly 55, and SOS⁡(PG)≤55\operatorname{SOS}(P_G)\le55.

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).

The base $G_0$ on the $21 \times 4$ grid with coloured tiles and arcs

Figure 1. The base G0G_0 on the 21×421 \times4 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 p=(10,1)p = (10,1) to c=(17,3)c = (17,3). 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 G0G_0 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 NcN_c of § 4 (since G0+{p,c}=Nc+{d,c}G_0+\{p,c\}=N_c+\{d,c\}), they say nothing about extensions of other extremal configurations.

2-edgecccertificateNQN_Qθ\thetaα+θε\alpha+ \theta\varepsilon
e1e_1(1,2)(1,2)contraction760.2352.4⋅10−112.4 \cdot10^{-11}
(1,4)(1,4)contraction760.0405.0⋅10−125.0 \cdot10^{-12}
e2e_2(2,1)(2,1)product relation (15 products)
(15,3)(15,3)product relation (13 products)
e3e_3(2,4)(2,4)product relation (4 products)
(12,1)(12,1)product relation (3 products)
e4e_4(3,1)(3,1)product relation (3 products)
(16,2)(16,2)product relation (4 products)
e5e_5(3,2)(3,2)product relation (4 products)
2-edgecccertificateNQN_Qθ\thetaα+θϵ\alpha+ \theta\epsilon
(14,1)(14,1)product relation (3 products)
e6e_6(4,3)(4,3)product relation (4 products)
(6,1)(6,1)product relation (3 products)
e7e_7(4,4)(4,4)contraction750.0535.3⋅10−125.3 \cdot10^{-12}
(8,1)(8,1)contraction750.2772.8⋅10−112.8 \cdot10^{-11}
e8e_8(5,2)(5,2)product relation (4 products)
(21,1)(21,1)product relation (3 products)
e9e_9(5,3)(5,3)product relation (6 products)
(12,2)(12,2)product relation (7 products)
e10e_{10}(6,3)(6,3)product relation (4 products)
(11,2)(11,2)product relation (5 products)
e11e_{11}(7,1)(7,1)product relation (10 products)
(12,3)(12,3)product relation (11 products)
e12e_{12}(7,3)(7,3)contraction770.0091.2⋅10−121.2 \cdot10^{-12}
(8,4)(8,4)contraction770.0616.3⋅10−126.3 \cdot10^{-12}
e13e_{13}(7,4)(7,4)contraction770.0495.0⋅10−125.0 \cdot10^{-12}
(8,3)(8,3)contraction770.1031.1⋅10−111.1 \cdot10^{-11}
e14e_{14}(9,1)(9,1)product relation (3 products)
(11,3)(11,3)product relation (4 products)
e15e_{15}(9,2)(9,2)product relation (10 products)
(10,3)(10,3)product relation (10 products)
e16e_{16}(9,3)(9,3)product relation (11 products)
(10,2)(10,2)product relation (2 products)
e17e_{17}(11,1)(11,1)product relation (3 products)
(14,3)(14,3)product relation (4 products)
e18e_{18}(13,1)(13,1)product relation (3 products)
(13,2)(13,2)product relation (4 products)
e19e_{19}(13,3)(13,3)product relation (9 products)
(14,2)(14,2)product relation (10 products)
e20e_{20}(15,1)(15,1)contraction750.0202.3⋅10−122.3 \cdot10^{-12}
(17,3)(17,3)contraction750.0263.3⋅10−123.3 \cdot10^{-12}
e21e_{21}(15,4)(15,4)contraction760.2072.1⋅10−112.1 \cdot10^{-11}
(16,4)(16,4)contraction760.0909.2⋅10−129.2 \cdot10^{-12}
e22e_{22}(16,1)(16,1)contraction750.0181.8⋅10−121.8 \cdot10^{-12}
(18,2)(18,2)contraction750.0464.6⋅10−124.6 \cdot10^{-12}
e23e_{23}(17,1)(17,1)contraction750.0272.7⋅10−122.7 \cdot10^{-12}
(19,3)(19,3)contraction750.0394.0⋅10−124.0 \cdot10^{-12}
e24e_{24}(17,4)(17,4)contraction760.1061.1⋅10−111.1 \cdot10^{-11}
(18,4)(18,4)contraction760.1181.3⋅10−111.3 \cdot10^{-11}
e25e_{25}(18,1)(18,1)contraction750.0282.9⋅10−122.9 \cdot10^{-12}
(20,2)(20,2)contraction750.0535.7⋅10−125.7 \cdot10^{-12}
e26e_{26}(19,1)(19,1)product relation (10 products)
(21,3)(21,3)product relation (9 products)
e27e_{27}(19,4)(19,4)contraction760.1831.9⋅10−111.9 \cdot10^{-11}
(20,4)(20,4)contraction760.0666.8⋅10−126.8 \cdot10^{-12}

Table 2. The 56 extensions {p,c}\{p,c\}, p=(10,1)p = (10,1), grouped by the old 2-edge {c,c′}\{c,c'\} of the base. For a product relation: the number of products frfsf_r f_s in the certified relation. For a contraction: the order NQN_Q of the reduced Gram block Q(h)Q(h), the contraction constant θ\theta and the bound α+θε\alpha+ \theta\varepsilon checked against ε=10−10\varepsilon= 10^{-10}. Decimal entries are rounded for display; the acceptance comparisons use the exact rational values in the supplementary data.

2-edgecccertificateNQN_Qθ\thetaα+θε\alpha+\theta\varepsilon
e28e_{28}(20,1)(20,1)contraction750.0272.7⋅10−122.7\cdot10^{-12}
(21,2)(21,2)contraction750.0495.2⋅10−125.2\cdot10^{-12}

Table 2 (PDF p. 7). Table 2, continued

Other extremal configurations

Replacing an old 2-edge {d,c}\{d,c\} of G0G_0 by {p,c}\{p,c\} gives a 55-square configuration NcN_c with its hole at dd. Of the 56 configurations NcN_c, 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 cc 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 (832)+83=3486\binom{83}{2}+83=3486 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 z2(21,4)z_2(21,4). Each certificate is accepted by a separate checker that does not import the generating program.

The configuration with c=(11,3)c=(11,3) is G0G_0 with rows 9 and 10 exchanged. The other five are pairwise non-isomorphic and not isomorphic to G0G_0 (exhaustive search over the 24 column permutations and all row bijections). A short invariant already separates one of them: G0G_0 has two 2-edges with both halves in one row, {(1,2),(1,4)}\{(1,2),(1,4)\} and {(13,1),(13,2)}\{(13,1),(13,2)\}, while the configuration with c=(13,2)c=(13,2) has only one. Hence the extremal configurations of z2(21,4)z_2(21,4) fall into at least six isomorphism classes, and the case H=0H=0 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 E⊆[m]×[n]E\subseteq[m]\times[n] be C4C_4-free with ∣E∣=m+(n2)|E|=m+\binom{n}{2}. 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 z2M(21,4)z_{2M}(21,4), where ∣E1∣=27=21+(42)|E_1|=27=21+\binom{4}{2}.

Proof. Let did_i be the degree of row ii. Since EE is C4C_4-free, distinct rows contain distinct pairs of columns, so ∑i(di2)≤(n2)\sum_i \binom{d_i}{2} \le\binom{n}{2}. With d≤1+(d2)d \le1 + \binom{d}{2} for every d≥0d \ge0,

m+(n2)=∑idi≤∑i(1+(di2))≤m+(n2).m + \binom{n}{2} = \sum_i d_i \le\sum_i \left(1 + \binom{d_i}{2}\right) \le m + \binom{n}{2}.

Equality throughout gives di=1+(di2)d_i = 1 + \binom{d_i}{2}, that is di∈{1,2}d_i \in\{1,2\}, and ∑i(di2)=(n2)\sum_i \binom{d_i}{2} = \binom{n}{2}, so the pairs of columns in the rows are all of them, each once.

This is the classical equality case of the counting behind z(m,n)≤m+(n2)z(m,n) \le m + \binom{n}{2}; we include the proof because it is short and checked in Isabelle (§ 7).

The six-to-four reduction

Lemma 7. Suppose an (SM)(S_M)-admissible display of length tt contains the 2-edges fi=xiyc+qf_i = x_i y_c + q and fj=xjyc+qf_j = x_j y_c + q with the same secondary monomial qq and i≠ji \ne j, and, for some column b≠cb \ne c and row k∉{i,j}k \notin\{i,j\}, the 1-edges ai=xiyba_i = x_i y_b, aj=xjyba_j = x_j y_b, u=xkycu = x_k y_c, v=xkybv = x_k y_b. Then SOS⁡(PG)≤t−2\operatorname{SOS}(P_G) \le t - 2.

Proof. Put F±=(fi±fj)/2F_{\pm} = (f_i \pm f_j)/\sqrt{2} and A±=(ai±aj)/2A_{\pm} = (a_i \pm a_j)/\sqrt{2}. Then F−=(xi−xj)yc/2F_{-} = (x_i - x_j)y_c/\sqrt{2} and A−=(xi−xj)yb/2A_{-} = (x_i - x_j)y_b/\sqrt{2}, so F−v=A−uF_{-}v = A_{-}u, and

fi2+fj2+ai2+aj2+u2+v2=F+2+A+2+(F−+v)2+(A−−u)2.f_i^2 + f_j^2 + a_i^2 + a_j^2 + u^2 + v^2 = F_{+}^2 + A_{+}^2 + (F_{-} + v)^2 + (A_{-} - u)^2.

Replace the six summands by the four on the right and keep the others.

Corollary 8. Let GG be an irreducible (SM)(S_M)-admissible configuration on m×nm \times n cells whose 1-edge graph is C4C_4-free with ∣E1∣=m+(n2)|E_1| = m + \binom{n}{2}. Then a shared secondary half has at most n−1n - 1 main halves in any one column, hence multiplicity at most n(n−1)n(n - 1). At 21×421 \times4, with ∣E1∣=27|E_1| = 27, the multiplicity is at most 12.

Proof. Fix a column cc and the rows i1,i2,…i_1,i_2,\ldots of the main halves in cc of the 2-edges at one secondary half. The 1-edges of row iri_r avoid column cc, which holds a main half, and by Lemma 6 each row has one or two 1-edges. If rows ir≠isi_r \ne i_s had 1-edges in a common column bb, then by Lemma 6 the pair {b,c}\{b,c\} lies in a row kk with 1-edges at (k,b)(k,b) and (k,c)(k,c); k∉{ir,is}k \notin\{i_r,i_s\} because (ir,c)(i_r,c) and (is,c)(i_s,c) 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 n−1n - 1 other columns.

Remark 9. The transposed form of Lemma 7, with two main halves (i,c)(i,c), (i,c′)(i,c') in one row, needs a row bb with 1-edges at (b,c)(b,c), (b,c′)(b,c') and (b,k)(b,k) for a third column kk. 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 GG be an extremal 55-square configuration of z2(21,4)z_2(21,4) with its unique hole p=(r0,c0)p = (r_0,c_0), and let S0S_0 be the set of columns of the 1-edges of row r0r_0. Among the 56 extensions of GG by one 2-edge at pp, exactly

∑b∈S0(deg⁡b−2)\sum_{b \in S_0} (\deg b - 2)

admit a direct application of Lemma 7 to the displayed representation, where deg⁡b\deg b is the number of 1-edges in column bb. Each of these extensions has SOS rank at most 54.

Proof. Since GG satisfies (S)(S), the only shared cell in the extension {p,c}\{p,c\} is cc, common to the new 2-edge and the old one {d,c}\{d,c\}; condition (SM)(S_M) forces cc to be secondary in both, with main halves pp and dd. The extension keeps E1E_1, so its rows still have at most two 1-edges, and by Remark 9 Lemma 7 applies only when d=(r,c0)d=(r,c_0) lies in column c0c_0 and rows r0r_0 and rr have 1-edges in a common column bb; then the row kbk_b of the pair {b,c0}\{b,c_0\} (Lemma 6) supplies (kb,b)(k_b,b) and (kb,c0)(k_b,c_0), and kb∉{r0,r}k_b\notin\{r_0,r\} since (r0,c0)(r_0,c_0) is the hole and (r,c0)(r,c_0) a half. Conversely, let r≠r0r\ne r_0 have a 1-edge in some b∈S0b\in S_0 and r≠kbr\ne k_b for all bb. Then (r,c0)(r,c_0) is not a 1-edge (otherwise rr would contain the pair {b,c0}\{b,c_0\}), and not a hole, so it is a half dd, and its extension is reduced. Each such row gives one extension. The rows with a 1-edge in some b∈S0b\in S_0 number ∑b∈S0deg⁡b−(∣S0∣−1)\sum_{b\in S_0}\deg b-(|S_0|-1), since a row with two columns of S0S_0 is the row r0r_0 of that pair; removing r0r_0 and the ∣S0∣|S_0| distinct rows kbk_b leaves ∑b∈S0(deg⁡b−2)\sum_{b\in S_0}(\deg b-2). 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 G0G_0, S0={4}S_0=\{4\} and deg⁡4=10\deg4=10, so Lemma 7 reduces 8 extensions by hand: c=(2,4),(16,2),(3,2),(4,3),(5,2),(11,3),(14,3),(13,2)c=(2,4),(16,2),(3,2),(4,3),(5,2),(11,3),(14,3),(13,2), all with b=4b=4 and kb=5k_b=5. This agrees with Table 2: all eight are certified there by product relations with four products each, the shape of the relation F−v−A−u=0F_{-v}-A_{-u}=0 of Lemma 7. The six configurations of Table 3 share the 1-edge graph of G0G_0, and in each of them the row of the new hole again has S0={4}S_0=\{4\}, so the count is deg⁡4−2=8\deg4-2=8 in every case.

kept half ccnew hole ddproducts fixed among occupied cellsclass
(9,3)(9,3)(10,2)(10,2)all 3486=(832)+833486=\binom{83}{2}+831
(11,3)(11,3)(9,1)(9,1)all 3486=(832)+833486=\binom{83}{2}+830
(9,2)(9,2)(10,3)(10,3)all 3486=(832)+833486=\binom{83}{2}+832
(10,3)(10,3)(9,2)(9,2)all 3486=(832)+833486=\binom{83}{2}+833
(13,3)(13,3)(14,2)(14,2)all 3486=(832)+833486=\binom{83}{2}+834
(13,2)(13,2)(13,1)(13,1)all 3486=(832)+833486=\binom{83}{2}+835

Table 3. The six irreducible 55-square configurations obtained from the base by replacing the old 2-edge {d,c}\{d,c\} by {p,c}\{p,c\}. Class: isomorphism class under row and column permutations (0 is the class of the base).

The column bound

For an SOS biquadratic form PP write P(x,ej)=xTQjxP(x,e_j)=x^{T}Q_jx. Then

SOS⁡(P)≤rank⁡Qj+BSR⁡(m,n−1).\operatorname{SOS}(P)\le\operatorname{rank}Q_j+\operatorname{BSR}(m,n-1).

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 P=∥∑i,ℓviℓxiyℓ∥2P=\left\|\sum_{i,\ell}v_{i\ell}x_i y_\ell\right\|^2, the vectors vijv_{ij}, 1≤i≤m1\le i\le m, span a space of dimension rank⁡Qj\operatorname{rank}Q_j, and the orthogonal projection onto it and onto its complement splits PP into a sum of at most rank⁡Qj\operatorname{rank}Q_j squares and an SOS form free of yjy_j. If (i0,j)(i_0,j) is an empty cell, vi0j=0v_{i_0j}=0 in every representation (its squared norm is the zero coefficient of xi02yj2x_{i_0}^2y_j^2), so rank⁡Qj≤20\operatorname{rank}Q_j\le20 and, with BSR⁡(21,3)=42\operatorname{BSR}(21,3)=42 [5 Theorem 1], SOS⁡(PG)≤62\operatorname{SOS}(P_G)\le62. This does not exclude an irreducible 56-square display, since 56≤6256\le62; and for H=0H=0 it gives only 21+42=6321+42=63.

Remark 11 (A 2×22\times2 example). Let a=x1y1a=x_1y_1, b=x1y2b=x_1y_2, c=x2y1c=x_2y_1, d=x2y2d=x_2y_2. The forms a2+(b+c)2a^2+(b+c)^2 and a2+(b+d)2a^2+(b+d)^2 each have a unique positive semidefinite Gram matrix (the zero diagonal entry of the empty cell fixes the only free parameter), and their union a2+(b+c)2+(b+d)2a^2+(b+c)^2+(b+d)^2, with every cell occupied, is not a sum of two squares: its matrix in yy has determinant 2x14+2x13x2+2x12x22+2x1x23+x242x_1^4+2x_1^3x_2+2x_1^2x_2^2+2x_1x_2^3+x_2^4, 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 21×421\times4 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 (e1,e2,s,k)=(27,29,27,2)(e_1,e_2,s,k)=(27,29,27,2); the second has (26,30,27,3)(26,30,27,3) 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 9.29⋅10−129.29 \cdot10^{-12} and 5.35⋅10−125.35 \cdot10^{-12}. 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.

statementIsabelle theorem
cell identity of Proposition 3display_cell_count, cell_count_21x4
t=56t = 56, H=0H = 0 gives k=1k = 1no_hole_one_share
heredity, Lemma 1irreducible_delete_square
Lemma 6 and the case 21×421 \times4c4_free_extremal_rows, every_column_pair_once_21x4
the identity of Lemma 7six_to_four
the 2×22 \times2 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 G0G_0, 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 G0G_0 without empty cells. By Proposition 3, an irreducible admissible 56-square configuration with H=0H = 0 is obtained by adjoining one 2-edge to an extremal 55-square configuration, and neither of its two cores is isomorphic to G0G_0. Excluding all of them requires a result for the other extremal configurations, of which there are at least five more classes. For H≥1H \ge1 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. [1]Z. Chen, Y. Chen, Recursive-Line Zarankiewicz Numbers with Four Columns, arXiv:2609.11093v2, 2026.arxiv.org/abs/2609.11093
  2. [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. [3]N. Lebedev, Asymptotic equivalence and exact values for second-order Zarankiewicz numbers, arXiv:2610.05442v1, 2026.arxiv.org/abs/2610.05442
  4. [4]J. Löfberg, L. Qi, Second Order Zarankiewicz Number, arXiv:2608.30555v3, 2026.arxiv.org/abs/2608.30555
  5. [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. [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. [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. [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

Paper details

vlnc:W_g6h3rma6
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

AI assistant

View statement
Looking for related papers…
Contents