Alphabeta Math
PropositionStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-31
How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

  • Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
  • AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
  • AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Polynomially related encodings preserve polynomial size bounds

Statement

Let σ,τ:I→{0,1}∗ be polynomially related encodings of the same instance set I. For any function m:I→N, the following are equivalent:

  1. There is a polynomial p such that m(x)≤p(∣x∣σ) for every x∈I.
  2. There is a polynomial r such that m(x)≤r(∣x∣τ) for every x∈I.

Facts & Assumptions

Given: Polynomially related encodings σ,τ:I→{0,1}∗ and a function m:I→N.

[L1]

The notation ∣x∣σ means ∣σ(x)∣, and polynomial relatedness means that there are polynomials q,s with ∣σ(x)∣≤q(∣x∣τ) and ∣τ(x)∣≤s(∣x∣σ) for all x∈I, by Instance size and polynomially related encodings.

Proof

technique · direct
1.1

Assume clause 1. Then there is a polynomial p with m(x)≤p(∣x∣σ) for all x∈I.

given
1.2

By [L1], there is a polynomial q with ∣x∣σ≤q(∣x∣τ) for all x∈I. Choose a polynomial P:N→N such that p(n)≤P(n) for every n and P is nondecreasing; for example, if p(t)=∑j=0dajtj, one may take P(t)=∑j=0d⌈∣aj∣⌉(t+1)j. Then m(x)≤p(∣x∣σ)≤P(∣x∣σ)≤P(q(∣x∣τ)) for every x∈I. Since P∘q is again a polynomial, clause 2 holds.

L1algebra
1.3

Conversely, assume clause 2. Then there is a polynomial r with m(x)≤r(∣x∣τ) for all x∈I.

given
1.4

By [L1], there is a polynomial s with ∣x∣τ≤s(∣x∣σ) for all x∈I. Choose a polynomial R:N→N such that r(n)≤R(n) for every n and R is nondecreasing. Then m(x)≤r(∣x∣τ)≤R(∣x∣τ)≤R(s(∣x∣σ)) for every x∈I. Since R∘s is a polynomial, clause 1 holds.

L1algebra
2.1

Steps 1.2 and 1.4 prove the two implications, so clauses 1 and 2 are equivalent.

step 1.2step 1.4∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

2 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources