Biquadratic SOS Rank and Double Zarankiewicz Number

This paper introduces the double Zarankiewicz number $z_2(m,n)$, defined via bipartite graphs allowing "double edges" corresponding to squared bilinear forms, to establish improved lower bounds for the maximum SOS rank of biquadratic forms $\operatorname{BSR}(m,n)$ and resolve the previously noted gap in the $4\times3$ case.

The Gist

Here is an explanation of the paper using simple language and creative analogies.

The Big Picture: Building with Math Bricks

Imagine you are an architect trying to build a sturdy tower using two types of materials:

1. Standard Bricks: These are simple, single blocks.
2. Double Bricks: These are special blocks made by gluing two standard bricks together side-by-side.

Your goal is to build the tallest possible tower (representing the "maximum complexity" of a mathematical object) without the tower collapsing. In the world of this paper, a "collapse" happens if you accidentally create a specific weak pattern called a C4-cycle (think of it as a square hole in the wall that makes the structure unstable).

For a long time, mathematicians thought the tallest tower they could build was limited by a famous rule called the Zarankiewicz Number. This rule said: "You can only use as many Standard Bricks as possible without forming a square hole."

However, the authors of this paper discovered a loophole. They found that by using Double Bricks (which represent a slightly more complex mathematical shape), they could build a tower that was taller than the old rules predicted, without creating any square holes.

The Characters in the Story

• The Biquadratic Form: Think of this as the Blueprint for your tower. It's a complex mathematical recipe that tells you how to combine variables (like $x$ and $y$) to create a shape.
• SOS Rank (Sum of Squares): This is the height of your tower. It counts how many "square" pieces you need to build the blueprint. The higher the rank, the more complex the shape.
• The Bipartite Graph: This is a map or a grid showing where you place your bricks. One side of the grid has rows (people), and the other has columns (chairs). A "brick" is placed where a person sits in a chair.
• The C4-Cycle: This is a forbidden square. If you have four bricks forming a perfect square on your map (Person A in Chair 1, Person A in Chair 2, Person B in Chair 1, Person B in Chair 2), the tower collapses. You must avoid this pattern.

The Old Rule vs. The New Discovery

The Old Rule (Zarankiewicz Number):
Mathematicians used to say, "To get the tallest tower, just pack in as many Standard Bricks (1-edges) as you can, as long as you don't make a square hole."

• Example: For a 4x3 grid, the old rule said the max height was 7.

The New Discovery (Double Zarankiewicz Number):
The authors realized, "Wait! What if we use Double Bricks (2-edges)? A Double Brick is like a single unit that covers two spots at once (e.g., a term like $(x_4y_2 + x_1y_3)^2$). It counts as one piece in our construction but occupies two spots on the map."

They found that by mixing Standard Bricks and Double Bricks, they could build a taller tower without making a square hole.

• The Breakthrough: For the 4x3 grid, they built a tower of height 8 (beating the old limit of 7) by adding one special Double Brick to the mix.

How They Defined the New Rules

To make sure their new towers were valid, they had to update the "No Square Hole" rule. They called this the Generalized C4-Cycle.

1. The Counting Rule: If you look at any small 2x2 section of your map, you can't have more than 3 "units" of weight.

   • A Standard Brick counts as 1.
   • A Double Brick counts as 2 (because it's two bricks glued together).
   • If a 2x2 section has 4 units of weight, it's a collapse.

2. The Logic Rule: They also checked the math to ensure the bricks weren't secretly canceling each other out. If the math showed that the bricks could be rearranged to form a smaller, simpler tower, then the original tower wasn't truly "tall" or "complex." They proved that if you follow the counting rule, the tower is genuinely tall and cannot be simplified.

The Results: What Did They Find?

The authors calculated the new maximum heights (the Double Zarankiewicz Numbers) for various grid sizes:

• Small Grids (2xN or Mx2): The new rule matches the old rule. No surprise here.
• 3x3 Grid: The max height is 6. (Same as before).
• 4x3 Grid: The max height is 8. (Old rule was 7. New record!)
• 5x3 Grid: The max height is 9. (Old rule was 8. New record!)
• 4x4 Grid: They found a tower of height 10. The old rule was 9. They suspect the absolute limit is either 10 or 11, but they haven't proven 11 yet. It's an open mystery!

Why Does This Matter?

This paper connects two different worlds of mathematics:

1. Graph Theory: The study of maps, networks, and connections (like social networks or subway maps).
2. Optimization & Algebra: The study of how to break down complex shapes into simpler parts (used in engineering, economics, and computer science).

By realizing that "Double Bricks" exist, the authors showed that our understanding of how complex these mathematical shapes can be was incomplete. They proved that you can pack more complexity into a system than previously thought, provided you use the right kind of building blocks.

The Takeaway

Think of the Zarankiewicz Number as the speed limit on a highway. For years, everyone thought the limit was 70 mph. This paper says, "Actually, if you drive a hybrid car (the Double Brick), you can safely go 80 mph without crashing, as long as you follow the new traffic rules."

They have drawn the new map, found the new speed limits for several towns, and left a few cities (like the 4x4 grid) as mysteries for future explorers to solve.

Technical Summary

Here is a detailed technical summary of the paper "Biquadratic SOS Rank and Double Zarankiewicz Number" by Liqun Qi, Chunfeng Cui, and Yi Xu.

1. Problem Statement and Motivation

Context:
The paper investigates the Sum-of-Squares (SOS) rank of biquadratic forms. An $m \times n$ biquadratic form $P(x, y)$ is a polynomial where the degree is 2 in $x$ and 2 in $y$. The SOS rank is the minimum number $r$ such that $P$ can be written as a sum of $r$ squares of bilinear forms. The maximum possible SOS rank for $m \times n$ forms is denoted as BSR($m, n$).

The Gap:
It was previously established that $BSR(m, n) \geq z(m, n)$, where $z(m, n)$ is the classical Zarankiewicz number (the maximum number of edges in a bipartite graph with no $C_4$ cycle).

• For small parameters like $(3,3)$, $(m,2)$, and $(2,n)$, the equality $BSR(m, n) = z(m, n)$ holds.
• However, a discrepancy was discovered for the **$4 \times 3$case**:$BSR(4, 3) \geq 8$, while the classical Zarankiewicz number is$z(4, 3) = 7$.
• This gap arises because the extremal form achieving rank 8 includes a term $(x_4y_2 + x_1y_3)^2$, which is the square of a bilinear form with two terms, rather than a single monomial square. This term does not correspond to a standard edge in the bipartite graph associated with the classical Zarankiewicz problem.

Objective:
The authors aim to explain this phenomenon by generalizing the Zarankiewicz problem to include "double edges" (representing squares of two-term bilinear forms) and to determine the exact lower bounds for $BSR(m, n)$ using this new framework.

2. Methodology and Definitions

The paper introduces a new combinatorial structure to model the SOS rank more accurately.

Double Bipartite Graphs:
The authors define a generalized bipartite graph $G = (S, T, E)$ where the edge set $E$ is the union of two types:

1. 1-edges ($E_1$): Standard edges $(i, j)$ corresponding to monomial squares $x_i^2 y_j^2$.
2. 2-edges ($E_2$): Hyper-edges of the form $(i, j; k, l)$ corresponding to the square of a two-term bilinear form $(x_i y_j + x_k y_l)^2$. Note that $i, k \in S$ and $j, l \in T$.

Doubly Simple Biquadratic Forms:
Associated with such a graph is a form:
$$P_G(x, y) = \sum_{(i,j) \in E_1} x_i^2 y_j^2 + \sum_{(i,j;k,l) \in E_2} (x_i y_j + x_k y_l)^2$$
The SOS rank of $P_G$ is $|E_1| + |E_2|$ if the form is irreducible (cannot be decomposed into fewer squares).

Generalized $C_4$-Cycle:
To ensure irreducibility, the authors define a generalized $C_4$-cycle. A graph contains one if:

1. Combinatorial Condition: There exists a $2 \times 2$ submatrix (defined by two rows and two columns) containing at least 4 "ordinary edges" (counting 1-edges as 1 and 2-edges as 2, provided both constituent cells of the 2-edge are in the submatrix).
2. Linear Algebra Condition: There exists a non-trivial linear dependence among the basis vectors corresponding to the edges within a specific $2 \times 2$ block.

Double Zarankiewicz Number ($z_2(m, n)$):
Defined as the maximum total number of edges ($|E_1| + |E_2|$) in an $m \times n$ bipartite graph that contains no generalized $C_4$-cycle.

3. Key Contributions and Theoretical Results

Theorem 2.4 (Fundamental Inequality):
The paper proves that for any $m, n \geq 2$:
$$BSR(m, n) \geq z_2(m, n)$$
Proof Sketch: If a graph $G$ has no generalized $C_4$-cycle, the associated form $P_G$ is irreducible. Therefore, its SOS rank is exactly the number of edges in $G$. Since $z_2(m, n)$ is the maximum such edge count, $BSR(m, n)$ must be at least this value.

Exact Values for Small Parameters:
The authors determine the exact values of $z_2(m, n)$ for several cases, resolving the previously known gaps:

• $z_2(m, 2) = m + 1$ and $z_2(2, n) = n + 1$ (Matches classical results).
• $z_2(3, 3) = 6$ (Matches classical $z(3,3)$).
• $z_2(4, 3) = 8$: This explains the gap. The construction uses 7 standard edges (forming a $C_4$-free graph) plus 1 "2-edge" $(4, 2; 1, 3)$, totaling 8. The 2-edge avoids creating a generalized $C_4$ because the linear independence condition holds.
• $z_2(5, 3) = 9$: Improved from the classical $z(5, 3) = 8$.

The $4 \times 4$ Case:

• Lower Bound: The authors construct a graph with 10 edges (8 1-edges and 2 2-edges) that avoids generalized $C_4$-cycles. Thus, $z_2(4, 4) \geq 10$.
• Upper Bound: Using a counting argument over all $2 \times 2$submatrices (36 total), they prove that the total weighted edge count$M = |E_1| + 2|E_2|$cannot exceed 12. This implies$|E_1| + |E_2| \leq 11$.
• Result: $10 \leq z_2(4, 4) \leq 11$. The exact value remains an open problem, though the authors conjecture it is 10.

4. Significance and Implications

1. **Resolution of the $4 \times 3$Gap:** The paper provides a rigorous combinatorial explanation for why$BSR(4, 3) = 8$despite$z(4, 3) = 7$. It shows that "squares of bilinear forms" act as "super-edges" that can increase the rank without violating the structural constraints of the underlying graph, provided the new "generalized$C_4$" constraints are met.
2. New Lower Bounds: The results improve the known lower bounds for the maximum SOS rank of biquadratic forms:
   • $BSR(4, 4) \geq 10$ (previously $\geq 9$).
   • $BSR(5, 3) \geq 9$ (previously $\geq 8$).
3. Bridge Between Fields: The work establishes a deep connection between Extremal Graph Theory (Zarankiewicz problem) and Real Algebraic Geometry (SOS representations). It suggests that the complexity of SOS representations is governed by a generalized graph-theoretic extremal problem.
4. Future Directions: The paper outlines open problems, including determining the exact value of $z_2(4, 4)$, investigating asymptotic behavior for large $m, n$, and developing algorithms to check for generalized $C_4$-cycles using linear algebra.

Summary of Results Table

Parameters	Classical $z(m,n)$	New Double $z_2(m,n)$	Status
$(m, 2)$	$m+1$	$m+1$	Exact
$(2, n)$	$n+1$	$n+1$	Exact
$(3, 3)$	$6$|$6$	Exact
$(4, 3)$	$7$| **$8$**	Exact (Gap Closed)
$(5, 3)$	$8$| **$9$**	Exact (Gap Closed)
$(4, 4)$	$9$| **$10 \leq z_2 \leq 11$**	Open (Lower bound improved)

In conclusion, the paper successfully generalizes the Zarankiewicz problem to capture the nuances of SOS rank in biquadratic forms, proving that allowing "double edges" (squares of bilinear forms) strictly increases the maximum possible rank in specific dimensions.