The Complete Extended Euclidean Scheme Is Not in Piecewise Arithmetic $\mathrm{AC}^0$

Amiel Ferman

REVIEW 2 major objections 5 minor 8 references

The Complete Extended Euclidean Scheme Is Not in Piecewise Arithmetic $\mathrm{AC}^0$

T0 review · 2 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Computing the complete extended Euclidean scheme for pairs of monic univariate polynomials over a characteristic-zero field is impossible for polynomial-size, constant-depth piecewise arithmetic circuits, even when only the full padded list

desk verdict Substantial new lower bound for the Euclidean algorithm in constant-depth algebraic circuits; fix the cited hierarchy's size bound before believing the main theorem. read the letter →

arxiv 2608.01987 v1 pith:MSLYYYPH submitted 2026-08-03 cs.CC

Amiel Ferman This is my paper

classification cs.CC MSC 68Q1768Q2513P15

keywords completeextendedEuclideanschemepiecewisearithmeticcircuitsconstant-depthHankeldeterminantscontinuantssubresultantsPadéapproximationalgebraiccircuitlowerbounds

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper proves that no polynomial-size, constant-depth piecewise arithmetic circuit—one equipped with select gates and divisions—can output the complete extended Euclidean scheme for monic univariate polynomials over a characteristic-zero field. The lower bound already applies to the simpler task of returning only the complete padded list of ordinary nonzero Euclidean remainders. The reason is that the middle of that transcript encodes a consecutive Hankel determinant, and the paper first shows that such Hankel determinants are outside ordinary constant-depth arithmetic. The proof works through an explicit degeneration that extracts the continuant polynomial from a Hankel determinant, then recovers that determinant from fixed coordinates of the Euclidean remainder sequence. If correct, the result separates complete Euclidean data from individual invariants like gcd or resultant, which do admit constant-depth piecewise algorithms.

What carries the argument

The argument is carried by three objects. The continuant K_n, defined by K_0=1, K_1=x_1, and K_n=x_n K_{n-1}+K_{n-2}, is complete for polynomial-size arithmetic formulas under the paper's effective degeneration relation, in which one polynomial is recovered as the constant coefficient of another after substituting affine Laurent forms in an auxiliary parameter. Consecutive Hankel determinants Δ_N=det(a_{i+j})_{0≤i,j<N} then enter through a new explicit degeneration K_n⪯DEG Δ_{n+1}: in the determinant expansion, the terms of lowest weight in ε are exactly matchings of a path, whose matching polynomial is the continuant. On the Euclidean side, the fixed-bound principal subresultant coefficient

What would settle it

Look at the actual lower bound in the hierarchy theorem cited in Section 3.4: if it is only ω(1) rather than n^{ω(1)} for depth D−1, the reduction in the continuant lower bound no longer contradicts polynomial size and the main theorem is unsupported. Alternatively, exhibit a polynomial-size, constant-depth piecewise circuit for the padded ordinary remainder list for all monic pairs over Q; by the paper's own implication this would yield an ordinary constant-depth circuit for Hankel determinants, directly contradicting Theorem 1.2.

Watch

Extended reading notes

Core claim

The central claim is that the complete Euclidean remainder scheme—the map returning all nonzero remainders, padded to a fixed length—is not in the class of polynomial-size, constant-depth piecewise arithmetic circuits, and therefore neither is the complete extended Euclidean scheme that additionally outputs quotients and Bézout coefficients. The proof establishes two transfer principles. First, the continuant family lies inside consecutive Hankel determinants via an effective Laurent degeneration whose constant coefficient is exactly the continuant. Second, on a nonempty Zariski-open set, a middle principal subresultant of the specially chosen pair (x^{2n}, a0 x^{2n-1}+...+1) equals, up to a

Load-bearing premise

The proof relies on an imported hierarchy theorem that, for every fixed depth D, supplies an explicit polynomial family computable at depth 2D but not by polynomial-size circuits of depth D−1; Section 3.4 states this as both an ω(1) and an n^{ω(1)} lower bound, and only the superpolynomial form makes the contradiction against polynomial-size circuits work.

Editorial extensions

If this is right

The complete ordinary Euclidean remainder list, not merely the full extended scheme, has no polynomial-size constant-depth piecewise arithmetic circuit over characteristic zero.
The complete polynomial continued-fraction expansion of a rational function is not computable in this circuit model.
The complete profile of fixed-bound principal subresultant coefficients is not computable in this model, even though individual resultants and related invariants are known to be easy.
Normalized subdiagonal Padé approximation, even when only the denominator polynomial is required, is not computable in this model on its nondegenerate domain.
The continuant family is complete for polynomial-size arithmetic formulas under the paper's degeneration relation, so its constant-depth hardness is a canonical obstruction: a constant-depth upper bound for continuants would collapse all such formulas into constant-depth arithmetic.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the proof stands, the obstacle is not algebraic complexity per se but completeness of the transcript: any output that exposes a middle Hankel determinant from the Euclidean data is likely hard, while coordinate projections such as gcd and resultant remain easy; one could test this by examining other 'complete transcript' versions of classical algorithms, such as all intermediate pivots in struc
The Padé consequence suggests that approximation problems inherit lower bounds from exact algebraic data in a robust way: the denominator alone already exposes a Hankel determinant through a telescoping product of determinantal ratios, which may transfer to matrix Padé approximation or rational interpolation.
The proof uses characteristic zero to obtain infinitely many interpolation points and a nonempty normal locus; an editorial guess is that the same obstruction persists over sufficiently large finite fields, though the current proof does not cover them.
The select-removal step is existential and does not provide an identity test, so the lower bound is non-uniform in an essential way: a constructive implementation of the reduction would need to decide which child of a select gate is correct.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

First, the substance: this paper proves something new and substantive. It gives an explicit degeneration from the continuant to consecutive Hankel determinants, and a separate reduction showing that the complete Euclidean remainder sequence would compute those determinants. Together with the adjacent-depth hierarchy, these imply that the complete extended Euclidean scheme is not in the Andrews–Wigderson piecewise constant-depth model. The combinatorial heart — matching terms in the Hankel determinant exactly correspond to the continuant — is clean and I found it convincing. The subresultant-to-Hankel identity and the fixed-coordinate extraction from the remainder list are carefully done. The paper is honest about what is imported and what is new.

The main soft spot is in Section 3.4. Theorem 3.8 imports the Limaye–Srinivasan–Tavenas hierarchy, but the proof cites [5, Theorem 5] twice with different strengths: first as 'has sizes ω(1)' and later as 'the n^{ω(1)} lower bound'. These are not equivalent. ω(1) only says the size grows unboundedly, so it does not contradict polynomial size. The contradiction in Theorem 3.11 requires the stronger n^{ω(1)} statement. I suspect this is a transcription slip — the LST theorem is likely superpolynomial — but the author has to verify the exact statement and align the two citations. If the imported theorem only gives ω(1), the continuant lower bound and Theorems 1.1–1.4 collapse. This is a load-bearing point, so the paper should be accepted conditionally and referees must check it.

Two smaller points. The translation from the linear-combination circuit model to the ordinary +,× model in Remark 3.7 is careful about size and about linear-combination gates, but it never states the product fan-in convention on either side. If the LST model allows only, say, fan-in-two products, the depth translation could be different. That is likely routine. Also, Lemma 3.9's formula unfolding produces size s^{D}, which is fine for fixed D, but the proof writes O((D+1)s^{D+1}) — no issue.

There is no circularity or parameter fitting here. The external theorems are used as black boxes, and the two new reductions are genuine.

Verdict: this paper deserves a serious referee. If the hierarchy citation is corrected and the product-fan-in point is clarified, it should be accepted. I would bring it to a reading group and cite it once the citation issue is resolved.

Referee Report

2 major / 5 minor

Summary. The paper proves that, over any field of characteristic zero, the complete extended Euclidean scheme for monic univariate polynomials cannot be computed by polynomial-size constant-depth piecewise arithmetic circuits in the Andrews-Wigderson select-gate model. The proof has three main steps. First, using the VPe-completeness of continuants and the adjacent-depth hierarchy for arithmetic circuits, it shows that the continuant family is not in AC^0_F. Second, it constructs an explicit effective Laurent degeneration extracting the continuant as the constant term of a consecutive Hankel determinant, transferring the lower bound to Hankel determinants. Third, it shows that a middle principal subresultant of a specially chosen pair equals the relevant Hankel determinant, and that this subresultant is recoverable from fixed coordinates of the complete padded Euclidean remainder sequence on a nonempty Zariski-open set; a generic select-gate removal and constant-depth division elimination then convert any PAC-AC^0_F algorithm for the complete remainder scheme into an AC^0_F circuit for Hankel determinants. The same mechanism is applied to complete polynomial continued fractions, complete principal-subresultant profiles, and normalized subdiagonal Padé denominators.

Significance. If the proof is correct, the paper resolves an open question left in Andrews-Wigderson and establishes a clean separation: single final invariants such as gcd or resultant may be piecewise constant-depth computable, but complete transcripts of the Euclidean algorithm are not. The main reductions are explicit and quantitative, with no parameter fitting or circularity: the continuant-Hankel degeneration and the Euclid-to-Hankel implication are genuinely new, and the paper is transparent about its nonuniform conventions and its reliance on external theorems. The main risk is the precise strength of the imported adjacent-depth hierarchy, which is quoted inconsistently in Section 3.4; this issue is load-bearing and must be resolved before the main theorem can be accepted.

major comments (2)

[Section 3.4, Theorem 3.8] The proof of the hierarchy theorem quotes [5, Theorem 5] as saying that every depth-(D-1) circuit computing Q_{D,s} 'has sizes ω(1)', then later states that the same theorem gives an 'n^{ω(1)} lower bound'. These are not equivalent: ω(1) is compatible with polynomial size, whereas n^{ω(1)} rules it out. This distinction is not cosmetic. Theorem 3.11 chooses D=d+5 and needs H^{(d+5)} to have no polynomial-size depth-(d+4) circuit; that conclusion requires a superpolynomial lower bound in the family index, not merely a lower bound that grows without bound in the size parameter. Since Theorem 3.11 feeds into Theorem 1.2, Theorem 1.3, and finally Theorem 1.1, the inconsistency at this point breaks the chain as written. The authors must state the exact form of [5, Theorem 5], verify whether it supplies a lower bound of s^{ω(1)} for size parameter s, and adjust the proof accordingly.
[Section 3.4, Theorem 3.8] Relatedly, the proof says 'for every fixed D≥2 and growing size parameters' and then defines H^{(D)}_n := Q_{D,n} for all sufficiently large n. If [5, Theorem 5] only provides polynomials Q_{D,s} for a sparse sequence of size parameters, the definition of an explicit family indexed by all n needs clarification. This is probably fixable by defining the family on the supported sizes and filling the remaining indices with arbitrary polynomials, but the current wording is imprecise at a point that is essential for the contradictory family in Theorem 3.11.

minor comments (5)

[Abstract] Typo: 'correspondexactly' should be 'correspond exactly'.
[Section 3.4] In the first paragraph, the phrase 'has sizesω(1)' has a missing superscript and spacing; this is related to the major comment and should be rewritten with the precise lower bound from [5].
[Section 2.2] Definition 2.2 says 'as in Andrews and Wigderson’s [1, Definitions 2.3]' but the model is described in [1, Definitions 2.3 and 2.4]; the citation should be adjusted for accuracy.
[Section 9] In the proof of Theorem 9.6, the notation Δ_{s,k} is introduced with k≥1, but Δ_{s,0}=1 is subsequently used in the telescoping product; stating the convention before first use would improve readability.
[Throughout] The hierarchy theorem is repeatedly called 'adjacent-depth', although after the translation from the linear-combination model the depth gap in the ordinary model is larger than one. The terminology is not incorrect in context, but a brief clarification would prevent confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the derivation is a chain of explicit reductions over external lower-bound theorems; the §3.4 quote inconsistency is a correctness risk, not circularity.

full rationale

The proof chain is: (1) an ordinary-AC^0 lower bound for the continuant, obtained by combining the external adjacent-depth hierarchy of Limaye–Srinivasan–Tavenas [5] with the external continuant universality of Bringmann–Ikenmeyer–Zuiddam [2]; (2) a fully explicit effective Laurent degeneration K_n ⪯_DEG Δ_{n+1} (Theorem 4.1), proved term-by-term via the matching expansion of the determinant; and (3) the Euclid-to-Hankel implication (Theorem 1.3), in which the middle principal subresultant is identified with a consecutive Hankel determinant and then recovered from fixed leading-coefficient coordinates of the Euclidean remainder sequence on a normal Zariski-open locus. None of these steps defines its target in terms of itself: the principal subresultant coefficients are independently defined determinants, the Hankel determinant is a fixed polynomial, and the recovery formula (11) is a proved identity, not an assumed output. No parameter is fitted to data and then renamed a prediction; the Laurent substitution in Theorem 4.1 is explicit and quantitatively effective rather than an ansatz imported by citation. There are no self-citations: the cited results [1], [2], [3], [5], [6] are all by other authors, so no load-bearing self-citation chain exists. The only notable issue is in Section 3.4, Theorem 3.8: the proof first quotes [5, Theorem 5] as saying every depth-(D−1) circuit computing Q_{D,s} 'has sizesω(1)', which would not contradict polynomial size, and then refers to 'the n^{ω(1)} lower bound of [5, Theorem 5]', which would. This is an internal-consistency/correctness matter that must be checked against the published source, and if the true theorem supplies only ω(1), Theorem 3.11 and hence the main theorem would collapse. But that would be a missing or misquoted external support, not circular reasoning: the argument does not reduce to its own input. Accordingly, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No numerical free parameters are fitted. The proof is parameter-free in the complexity-theoretic sense, with only construction parameters such as the hierarchy depth D chosen from the assumed continuant depth. The central claim rests on four external theorems and the characteristic-zero assumption. No new mathematical entities are postulated.

assumptions (5)

standard math Limaye-Srinivasan-Tavenas adjacent-depth hierarchy: for each fixed D, H^(D) has polynomial-size depth 2D circuits but no polynomial-size depth D-1 circuits, with an n^{omega(1)} lower bound.
The entire continuant lower bound in Theorem 3.11 rests on this imported hierarchy theorem. The paper quotes it inconsistently in Section 3.4 as both 'sizes omega(1)' and 'n^{omega(1)}'.
standard math Bringmann-Ikenmeyer-Zuiddam continuant universality: every family in VPe is an effective degeneration of the continuant.
Used in Theorem 3.6 to transfer any constant-depth upper bound on the continuant to all of VPe. The quantitative version with polynomial Laurent exponents is proved in Proposition 3.5.
standard math Brent's formula balancing: a polynomial-size formula can be balanced to depth O(log n).
Used in Theorem 3.6 to turn formula size bounds into depth O(log n) before applying the quantitative continuation simulation.
standard math Andrews-Wigderson depth-preserving division elimination and select-removal results.
Used in Lemma 2.4 and Theorem 1.3 to remove divisions and select gates without losing polynomial size or constant depth.
domain assumption The base field F has characteristic zero.
The main theorem is stated only for characteristic zero. Char(F) not equal to 2 is needed in Proposition 3.5, and the nonemptiness argument in Lemma 6.2 uses rationality and positivity over the rationals.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The Complete Extended Euclidean Scheme Is Not in Piecewise Arithmetic $\mathrm{AC}^0$." pith.science (2026). https://pith.science/paper/MSLYYYPH

@misc{pith2026260801987,
  author       = {Pith},
  title        = {Pith review of: The Complete Extended Euclidean Scheme Is Not in Piecewise Arithmetic $\mathrmAC^0$},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MSLYYYPH}},
  note         = {Machine review of arXiv:2608.01987}
}

read the original abstract

We prove that the complete extended Euclidean scheme for pairs of monic univariate polynomials over a field of characteristic zero cannot be computed by polynomial-size, constant-depth piecewise arithmetic circuits in the select-gate model of Andrews and Wigderson. In fact, the lower bound already holds for the simpler task of outputting the complete padded list of nonzero Euclidean remainders. We show that a suitable Hankel determinant can be recovered from fixed coordinates of the complete Euclidean remainder sequence on a nonempty Zariski-open set. The connection is provided by a middle principal subresultant coefficient. A generic removal of select gates, followed by constant-depth division elimination, would therefore turn any piecewise constant-depth algorithm for the complete remainder sequence into an ordinary constant-depth circuit for Hankel determinants, contradicting the lower bound above. We also show that the same obstruction applies to several related outputs. It yields lower bounds for the complete polynomial continued-fraction expansion and for the complete profile of fixed-bound principal subresultant coefficients, since each of these outputs directly exposes the Hankel determinant used in the Euclidean reduction. In addition, we obtain a lower bound for normalized subdiagonal Pad'e approximation: even the normalized denominator alone suffices, through polynomially many parallel Pad'e computations and a telescoping product of determinantal ratios, to recover the same consecutive Hankel determinant. Consequently, none of these problems can be computed by polynomial-size, constant-depth piecewise arithmetic circuits.

Figures

Figures reproduced from arXiv: 2608.01987 by the authors.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

8 extracted references · 1 canonical work pages

[1]

Andrews and A

R. Andrews and A. Wigderson,Constant-Depth Arithmetic Circuits for Linear Algebra Problems, SIAM Journal on Computing, published online 2026. DOI: 10.1137/24M1708085. Preprint: arXiv:2404.10839, version dated September 22, 2025

arXiv 2026
[2]

Bringmann, C

K. Bringmann, C. Ikenmeyer, and J. Zuiddam,On Algebraic Branching Programs of Small Width, Journal of the ACM 65(5), Article 32, 2018. DOI: 10.1145/3209663

doi:10.1145/3209663 2018
[3]

R. P. Brent,The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM 21(2), 201–206, 1974. DOI: 10.1145/321812.321815

arXiv 1974
[4]

W. S. Brown and J. F. Traub,On Euclid’s Algorithm and the Theory of Subresultants, Journal of the ACM 18(4), 505–514, 1971. DOI: 10.1145/321662.321665

arXiv 1971
[5]

Limaye, S

N. Limaye, S. Srinivasan, and S. Tavenas,Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits, Journal of the ACM 72(4), Article 26, 2025. DOI: 10.1145/3734215

doi:10.1145/3734215 2025
[6]

Strassen,Vermeidung von Divisionen, Journal für die reine und angewandte Mathematik 264, 184–202, 1973

V. Strassen,Vermeidung von Divisionen, Journal für die reine und angewandte Mathematik 264, 184–202, 1973. DOI: 10.1515/crll.1973.264.184

doi:10.1515/crll.1973.264.184 1973
[7]

von zur Gathen,Parallel Algorithms for Algebraic Problems, SIAM Journal on Computing 13(4), 802–824, 1984

J. von zur Gathen,Parallel Algorithms for Algebraic Problems, SIAM Journal on Computing 13(4), 802–824, 1984. DOI: 10.1137/0213050

work page doi:10.1137/0213050 1984
[8]

von zur Gathen and J

J. von zur Gathen and J. Gerhard,Modern Computer Algebra, 3rd ed., Cambridge University Press, 2013. 45

2013

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.

[1] [1]

Andrews and A

R. Andrews and A. Wigderson,Constant-Depth Arithmetic Circuits for Linear Algebra Problems, SIAM Journal on Computing, published online 2026. DOI: 10.1137/24M1708085. Preprint: arXiv:2404.10839, version dated September 22, 2025

arXiv 2026

[2] [2]

Bringmann, C

K. Bringmann, C. Ikenmeyer, and J. Zuiddam,On Algebraic Branching Programs of Small Width, Journal of the ACM 65(5), Article 32, 2018. DOI: 10.1145/3209663

doi:10.1145/3209663 2018

[3] [3]

R. P. Brent,The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM 21(2), 201–206, 1974. DOI: 10.1145/321812.321815

arXiv 1974

[4] [4]

W. S. Brown and J. F. Traub,On Euclid’s Algorithm and the Theory of Subresultants, Journal of the ACM 18(4), 505–514, 1971. DOI: 10.1145/321662.321665

arXiv 1971

[5] [5]

Limaye, S

N. Limaye, S. Srinivasan, and S. Tavenas,Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits, Journal of the ACM 72(4), Article 26, 2025. DOI: 10.1145/3734215

doi:10.1145/3734215 2025

[6] [6]

Strassen,Vermeidung von Divisionen, Journal für die reine und angewandte Mathematik 264, 184–202, 1973

V. Strassen,Vermeidung von Divisionen, Journal für die reine und angewandte Mathematik 264, 184–202, 1973. DOI: 10.1515/crll.1973.264.184

doi:10.1515/crll.1973.264.184 1973

[7] [7]

von zur Gathen,Parallel Algorithms for Algebraic Problems, SIAM Journal on Computing 13(4), 802–824, 1984

J. von zur Gathen,Parallel Algorithms for Algebraic Problems, SIAM Journal on Computing 13(4), 802–824, 1984. DOI: 10.1137/0213050

work page doi:10.1137/0213050 1984

[8] [8]

von zur Gathen and J

J. von zur Gathen and J. Gerhard,Modern Computer Algebra, 3rd ed., Cambridge University Press, 2013. 45

2013