definitionnovel

Layout of partitions, measurements, and polynomial rows

Definition·def:layout·§3.2 The required rows, partitions, and measurements

Statement (paper)

For the factor scopes (If)f∈F(I_f)_{f\in\mathcal F}, let r⩾2r\ge2, D⩾1D\ge1, and 1⩽R<Q1\le R<Q be integers, and let 0<τ⩽1/20<\tau\le1/2. We require the following data and properties. \begin{enumerate} \item For each t∈[Q]t\in[Q], a partition [n]=St,1⊔⋯⊔St,r[n]=S_{t,1}\sqcup\cdots\sqcup S_{t,r}, allowing empty parts, with ∣St,g∣⩽2n/r|S_{t,g}|\le2n/r. \item For every factor f∈Ff\in\mathcal F, a sequence σf∈[r]Q\sigma_f\in[r]^Q. The value σf(t)\sigma_f(t) assigns factor ff to a group at point tt. \item For every t∈[Q]t\in[Q] and g∈[r]g\in[r], an integer matrix Ct,g∈Z[ct,g]×St,gC_{t,g}\in\mathbb Z^{[c_{t,g}]\times S_{t,g}}, where ct,gc_{t,g} is a nonnegative integer. Each row has sum of absolute values at most DD, and ∑g=1rct,g⩽2τn. \sum_{g=1}^r c_{t,g}\le2\tau n. For an assignment xx, the entries of Ct,g(x∣St,g)C_{t,g}(x|_{S_{t,g}}) are the measurements on group gg. \item For every f∈Ff\in\mathcal F and v∈Ifv\in I_f, a row P⃗f,v(T)∈Q[T]1×n\vec{P}_{f,v}(T)\in\mathbb Q[T]^{1\times n} with P⃗f,v(0)=δv\vec{P}_{f,v}(0)=\delta_v and deg⁡P⃗f,v⩽R\deg \vec{P}_{f,v}\le R. For every t∈[Q]t\in[Q], g∈[r]∖{σf(t)}g\in[r]\setminus\{\sigma_f(t)\}, and ξ∈QSt,g\xi\in\mathbb Q^{S_{t,g}}, require Ct,gξ=0⃗⟹⟨P⃗f,v(t),ξ~⟩=0, C_{t,g}\xi=\vec{0}\quad\Longrightarrow\quad \langle \vec{P}_{f,v}(t), \widetilde\xi\rangle=0, where ξ~∈Qn\widetilde\xi\in\mathbb Q^n is the extension of ξ\xi by zero. \item With dden=(R−1)!Q!d_{\mathrm{den}}=(R-1)!Q!, every coefficient of ddenP⃗f,vd_{\mathrm{den}} \vec{P}_{f,v} is an integer with O(Qlog⁡Q+log⁡D)O(Q\log Q+\log D) bits, with an absolute implied constant. \end{enumerate}

In plain English

A layout is the data: for each of QQ points tt, a partition of [n][n] into rr parts of size at most 2n/r2n/r; for each factor ff, a group assignment σf∈[r]Q\sigma_f\in[r]^Q; for each t,gt,g, an integer measurement matrix Ct,gC_{t,g} with row weights at most DD and total row count at most 2τn2\tau n over gg; and for each ff and v∈Ifv\in I_f, a rational polynomial row P⃗f,v(T)\vec P_{f,v}(T) of degree at most RR with P⃗f,v(0)=δv\vec P_{f,v}(0)=\delta_v. The row must vanish on any ξ\xi killed by Ct,gC_{t,g} whenever g≠σf(t)g\ne\sigma_f(t), and ddenP⃗f,vd_{\mathrm{den}}\vec P_{f,v} has integer coefficients with O(Qlog⁡Q+log⁡D)O(Q\log Q+\log D) bits, where dden=(R−1)!Q!d_{\mathrm{den}}=(R-1)!Q!.

Why it's here

This definition fixes the interface that the counting propositions assume: it says what a design must supply, so the counting routines can be stated for any design meeting these conditions. The key condition is that at each point tt, the evaluation of P⃗f,v(t)\vec P_{f,v}(t) is invisible to the measurements of every group except the one ff is assigned to. The few measurements (at most 2τn2\tau n in total) and the small bit-size bound on coefficients are what keep the counting cost and arithmetic under control.
Classified novel:
This interface (partitions, group assignments, sparse measurement matrices and polynomial rows that are invisible to every non-assigned group's measurements) is the paper's own framework for its subexponential counting scheme. No prior known construction supplies a layout of this kind; it encodes the paper's central new idea rather than adapting a standard definition.

Uses

Nothing else in the paper

Used by

propGeneral counting routine and its costpropCost of counting solutions via factor evaluation

Sources

PaperOpen
Section
§3.2 The required rows, partitions, and measurements
Page
—
Label
def:layout
Line
main_full_version.tex:1714
Leannot aligned

Phase 2 aligns this node to a Lean declaration.