Rank bounds for grid tensor decompositions

A grid tensor can enforce matching labels along edges by assigning 1 when both ends of every edge carry the same label and 0 otherwise. A cut rearranges the tensor into a matrix, with the labels on one side indexing rows and the rest indexing columns. How small can the sum of the smaller row-cut and column-cut ranks be when the tensor is written as a sum of arbitrary terms?

Why it matters and what counts as progress

Why it matters: The two matrix ranks constrain how efficiently a decomposition can represent the same grid constraints using row or column groupings. Correlations between terms matter in grid-based algorithms that count satisfying assignments.

What counts as progress: Prove a stronger lower bound for a specified grid and pair of cuts, or construct a decomposition that reaches the bound. For a network-cost result, specify how the network is grouped and charged.

How the problem developed

  1. 26 Oct 2026 · Grid counting methods [1][3]

    Anthropic and OpenAI The reported subexponential counting algorithms prompted study of limits on the ways local constraints can be grouped.

  2. 30 Oct 2026 · Bounds for product terms [2]

    Ruhollah Majdoddin Bounded a class of grid recursions built from product terms and asked what happens when the terms can be correlated.

  3. 6 Nov 2026 · Rank bound for arbitrary summands [3][4]

    Vaibhav Tulsyan with Claude Gave the smaller-cut rank-sum bound for a 3×33 \times 3 grid tensor. Tulsyan reports that Lean checked the inequality.

AI contribution

What the ETH refutations do not give: barriers for the counting engines, with machine-checked lemmas

Vaibhav Tulsyan

For the graph tensor on a 3×33 \times 3 grid with 18 edges joining cells in different rows and columns, take any finite sum of tensors equal to the graph tensor over a field. For each summand, take the smaller of the two matrix ranks obtained by cutting off the last row or the last column. If the edge labels range over a nonempty alphabet of size NN, the sum of these smaller ranks is at least N8N^8.

AI involvementAI-led
ImportanceNotable
Technical verificationFormal (Lean 4)
Human understandingFew
Paper date:

Sources

  1. ETH community examination
  2. Majdoddin’s grid-recursion bounds
  3. Tulsyan’s manuscript, Theorem 4.11
  4. Lean declaration for the 3×33 \times 3 rank bound
  5. Tulsyan’s research statement and AI disclosure
Publication history