pith. sign in

arxiv: 2603.04912 · v4 · submitted 2026-03-05 · 🧮 math.OC

Biquadratic SOS Rank and Augmented Zarankiewicz Number

Liqun Qi , Chunfeng Cui , Yi Xu This is my paper

Pith reviewed 2026-05-15 15:50 UTC · model grok-4.3

classification 🧮 math.OC
keywords biquadratic formssum-of-squares rankZarankiewicz numberbipartite graphsaugmented graphsextremal graph theorypolynomial optimization
0
0 comments X

The pith

The maximum biquadratic sum-of-squares rank is bounded below by the augmented Zarankiewicz number, which itself exceeds the classical Zarankiewicz number in some cases.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper defines the augmented Zarankiewicz number z_A(m,n) and the limited version z_L(m,n) from bipartite graphs that allow both ordinary 1-edges and paired 2-edges representing squares of binomials. It proves the chain BSR(m,n) is at least z_A(m,n) which is at least z_L(m,n) which is at least the classical z(m,n). Exact values of z_L are found for all (m,2) and the small cases (3,3), (4,3), (4,4), plus new lower bounds for (5,3) through (5,5). These give concrete improved estimates on how large the SOS rank of a biquadratic form can be.

Core claim

The maximum biquadratic SOS rank BSR(m,n) satisfies the inequality chain BSR(m,n) ≥ z_A(m,n) ≥ z_L(m,n) ≥ z(m,n), where z_A and z_L arise as the maximum number of edges in augmented bipartite graphs with 1-edges and 2-edges. Exact values of z_L(m,n) are determined for (m,2), (3,3), (4,3) and (4,4), with new lower bounds supplied for (5,3), (5,4) and (5,5).

What carries the argument

The augmented Zarankiewicz number z_A(m,n), the largest number of edges (counting 1-edges singly and 2-edges as pairs) that can be placed in an augmented bipartite graph with parts of sizes m and n without creating a forbidden configuration.

If this is right

  • z_L(m,n) is strictly larger than the classical Zarankiewicz number z(m,n) for several small pairs (m,n).
  • Improved explicit lower bounds are obtained for the maximum SOS rank of biquadratic forms in dimensions up to five.
  • Exact combinatorial values are now known for the limited augmented number in all (m,2) cases and the listed small square cases.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Graph constructions that achieve high z_L values directly produce biquadratic forms whose SOS rank is at least that value.
  • The same augmentation idea of allowing paired edges for binomial squares might be adapted to obtain lower bounds for SOS ranks of higher-degree forms.
  • These refined graph parameters could be used to test whether certain biquadratic forms arising in optimization problems require large SOS ranks.

Load-bearing premise

The correspondence between biquadratic SOS decompositions and selections of 1-edges and 2-edges in the augmented bipartite graph is faithful enough to preserve the stated rank inequalities.

What would settle it

A biquadratic form whose sum-of-squares rank is strictly less than the computed z_L(4,4) or z_L(5,5) would show the inequality chain does not hold.

Figures

Figures reproduced from arXiv: 2603.04912 by Chunfeng Cui, Liqun Qi, Yi Xu.

Figure 1
Figure 1. Figure 1: Illustrations of nondegenerate, row-degenerate, and column-degenerate 2-edges. [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: An example that Condition 3 in Definition 2.1 is triggered in the nondegenerate, row-degenerate, and [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: An illustration of the 4 × 3 augmented bipartite graph in (9) with SOS rank 8. Here, each solid line represents a 1-edge, and the two dotted lines represent the 2-edge (4,2; 1,3). k ∈ [4] and k /∈ {4, 1}, we have k ∈ {2, 3}. Since l ∈ [3] and l /∈ {2, 3}, we have l = 1. Thus the only candidates are (k, l) = (2, 1) and (3, 1). For (k, l) = (2, 1): • (2, 1): not in E1, not a half of any 2-edge ⇒ not occupied… view at source ↗
Figure 4
Figure 4. Figure 4: An illustration of the 4 × 4 biquadratic form in Theorem 4.1 with SOS rank 10. Here, each solid line represents a 1-edge, and the two dotted lines represent a 2-edge (2,3;4,2). 4 The 4 × 4 Case We now determine the exact value of the limited augmented Zarankiewicz num￾ber for m = n = 4. Theorem 4.1. zL(4, 4) = 10. Proof. We prove the lower and upper bounds separately. Lower bound zL(4, 4) ≥ 10. We construc… view at source ↗
read the original abstract

This paper introduces the concepts of the augmented Zarankiewicz number $z_A(m,n)$ and the limited augmented Zarankiewicz number $z_L(m,n)$, which are natural combinatorial extensions of the classical Zarankiewicz number. These numbers arise from augmented bipartite graphs that may contain both standard edges (1-edges) and pairs of edges representing squares of binomials (2-edges). The main theoretical result establishes the inequality chain $\operatorname{BSR}(m, n) \geq z_A(m, n) \geq z_L(m, n) \geq z(m, n)$, linking the maximum biquadratic sum-of-squares (SOS) rank to these extremal graph parameters. We determine the exact values of $z_L(m, n)$ for the cases $(m,2)$, $(3,3)$, $(4, 3)$ and $(4,4)$, and provide new lower bounds for the cases $(5,3)$, $(5,4)$, and $(5,5)$. These results yield improved lower bounds for the maximum SOS rank of biquadratic forms, demonstrating that $z_L(m,n)$ can exceed the classical Zarankiewicz number, thereby offering a refined combinatorial perspective on the SOS rank problem.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper introduces the augmented Zarankiewicz number z_A(m,n) and limited augmented Zarankiewicz number z_L(m,n) via augmented bipartite graphs containing 1-edges and 2-edges (the latter representing squares of binomials). It establishes the inequality chain BSR(m,n) ≥ z_A(m,n) ≥ z_L(m,n) ≥ z(m,n) and computes exact values of z_L(m,n) for the cases (m,2), (3,3), (4,3) and (4,4), together with new lower bounds for (5,3), (5,4) and (5,5). These yield improved lower bounds on the maximum biquadratic sum-of-squares rank.

Significance. If the algebraic-combinatorial correspondence is valid, the work supplies a refined graph-theoretic method for lower-bounding biquadratic SOS ranks, with concrete exact values for small parameters that strictly exceed the classical Zarankiewicz number. The explicit constructions and bounds constitute a tangible advance for the SOS-rank problem in optimization.

major comments (1)
  1. [Main theoretical result (inequality chain)] The direction BSR(m,n) ≥ z_A(m,n) in the main inequality chain rests on a claimed correspondence between biquadratic SOS decompositions and augmented graphs. The manuscript must explicitly verify that every 2-edge (square of a binomial) contributes exactly two to the SOS rank without introducing algebraic dependencies among the terms, and that every valid SOS decomposition arises from some 1-edge/2-edge configuration. This bijection is load-bearing for the entire chain and is not fully substantiated by the abstract alone.
minor comments (2)
  1. [Abstract] The abstract employs BSR(m,n) and z(m,n) without a parenthetical definition or forward reference; a single sentence clarifying these quantities would improve readability.
  2. [Exact computations section] For the exact value of z_L(4,4), an explicit listing of the optimal augmented graph (number of 1-edges and 2-edges) would allow immediate verification of the claimed rank.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback. We address the concern about the correspondence underlying the inequality chain BSR(m,n) ≥ z_A(m,n) below.

read point-by-point responses

  1. Referee: [Main theoretical result (inequality chain)] The direction BSR(m,n) ≥ z_A(m,n) in the main inequality chain rests on a claimed correspondence between biquadratic SOS decompositions and augmented graphs. The manuscript must explicitly verify that every 2-edge (square of a binomial) contributes exactly two to the SOS rank without introducing algebraic dependencies among the terms, and that every valid SOS decomposition arises from some 1-edge/2-edge configuration. This bijection is load-bearing for the entire chain and is not fully substantiated by the abstract alone.

    Authors: We agree that the abstract is necessarily concise and does not contain the full verification. The manuscript establishes the required correspondence in Section 3 and the proof of Theorem 2.1. Each 2-edge is defined to correspond to a binomial square (x_i + x_j)^2 whose expansion produces exactly two distinct quadratic monomials; these monomials are linearly independent over the chosen support and introduce no algebraic relations that would reduce the SOS rank below two. The converse direction is shown by associating every term in a valid biquadratic SOS decomposition with either a 1-edge (for a single monomial square) or a 2-edge (for a binomial square), yielding an augmented graph whose size equals the rank. We will revise the introduction to include a short paragraph outlining this explicit bijection, making the load-bearing step more transparent without altering the technical content. revision: yes

Circularity Check

0 steps flagged

No circularity: inequality chain follows from explicit graph-SOS constructions

full rationale

The paper defines z_A(m,n) and z_L(m,n) directly from the structure of augmented bipartite graphs (1-edges and 2-edges) and establishes BSR(m,n) ≥ z_A(m,n) by showing that any biquadratic SOS decomposition of rank r yields an augmented graph whose extremal parameter is at least r. This is a standard one-directional combinatorial encoding, not a self-definition or fitted-parameter renaming. No load-bearing self-citations, uniqueness theorems, or ansatz smuggling appear in the derivation; the exact values for small (m,n) are computed combinatorially and only tighten the lower bound side. The chain is therefore self-contained against external graph-theoretic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 2 invented entities

The central claim rests on the newly introduced graph parameters and the asserted correspondence to SOS rank; no free parameters are fitted and the axioms are standard combinatorial and algebraic facts.

axioms (1)
  • domain assumption Bipartite graphs with 1-edges and 2-edges model biquadratic SOS decompositions
    Invoked to establish the inequality chain between BSR and the new Zarankiewicz-type numbers.
invented entities (2)
  • augmented Zarankiewicz number z_A(m,n) no independent evidence
    purpose: Extremal function counting maximum edges in augmented bipartite graphs
    Newly defined to capture 2-edges representing binomial squares.
  • limited augmented Zarankiewicz number z_L(m,n) no independent evidence
    purpose: Restricted version allowing exact computation for small m,n
    Introduced to obtain concrete values and improved SOS-rank bounds.

pith-pipeline@v0.9.0 · 5520 in / 1378 out tokens · 45258 ms · 2026-05-15T15:50:09.446535+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

  1. [1]

    Low-rank sum- of-squares representations on varieties of minimal degree

    G. Blekherman, D. Plaumann, R. Sinn and C. Vinzant, “Low-rank sum- of-squares representations on varieties of minimal degree”,International Mathematics Research Notices2019(2019) 33-54

    work page 2019

  2. [2]

    Sums of squares and quadratic persistence on real projective varieties

    G. Blekherman, R. Sinn, G. Smith and M. Velasco, “Sums of squares and quadratic persistence on real projective varieties”,Journal of the European Mathematical Society24(2021) 925-965

    work page 2021

  3. [3]

    Bollob´ as,Extremal Graph Theory, Dover Publications, Mineola, NY, 2004

    B. Bollob´ as,Extremal Graph Theory, Dover Publications, Mineola, NY, 2004

    work page 2004

  4. [4]

    Zarankiewicz numbers near the triple system threshold

    G. Chen, D. Horsley and A. Mammoliti, “Zarankiewicz numbers near the triple system threshold”,Journal of Combinatorial Design32(2024) 556- 576

    work page 2024

  5. [5]

    The SOS rank of a 5×4 biquadratic form via orthogonalty

    Y. Chen, “The SOS rank of a 5×4 biquadratic form via orthogonalty”, manuscript, 2026

    work page 2026

  6. [6]

    The Sum of squares rank of biquadratic forms and the Zarankiewicz number

    C. Cui, L. Qi and Y. Xu, “The Sum of squares rank of biquadratic forms and the Zarankiewicz number”, February 2026, arXiv:2602.07844v2

    work page arXiv 2026

  7. [7]

    A many-facetted problem of Zarankiewicz

    R.K. Guy, “A many-facetted problem of Zarankiewicz”, in: G. Chartrand and S.F. Kapoor eds.,The Many Facets of Graph Theory, Springer, Berlin. 1969, pp. 129-141

    work page 1969

  8. [8]

    On the boundedness of degenerate hypergraphs

    J. Hou, C. Hu, H. Li, X. Liu, C. Yang and Y. Zhang, “On the boundedness of degenerate hypergraphs”,Acta Mathematica Sinica-English Series42 (2026) 464-480

    work page 2026

  9. [9]

    Cycles of given lengths in hypergraphs

    T. Jiang and J. Ma, “Cycles of given lengths in hypergraphs”,Journal of Combinatorial Theory, Series B133(2018) 54-77

    work page 2018

  10. [10]

    On a problem of K. Zarankiewicz

    T. K˝ ov´ ari, V. S¨ os, and P. Tur´ an, “On a problem of K. Zarankiewicz”, Colloquium Mathematicum3(1954) 50-57. 26

    work page 1954

  11. [11]

    Sum of squares decompositions and rank bounds for biquadratic forms

    L. Qi, C. Cui and Y. Xu, “Sum of squares decompositions and rank bounds for biquadratic forms”,Mathematics14(2026) No. 635

    work page 2026

  12. [12]

    ¨Uber ein Problem von K. Zarankiewicz

    I. Reiman, “ ¨Uber ein Problem von K. Zarankiewicz”,Acta Mathematica Academiae Scientiarum Hungaricae9(1958) 269-273

    work page 1958

  13. [13]

    Narrowing the Gap: SOS Ranks of 4×3 Biquadratic Forms and a Lower Bound of 8

    Y. Xu, C. Cui and L. Qi, “Narrowing the Gap: SOS Ranks of 4×3 Biquadratic Forms and a Lower Bound of 8”, February 2026, arXiv:2602.21570v1

    work page arXiv 2026

  14. [14]

    Problem P 101

    K. Zarankiewicz, “Problem P 101”,Colloquium Mathematicum2(1951) 301. 27

    work page 1951