Provable Advantages of Convolutional Arithmetic Circuits

Research-attempt provenance

Definitions and mathematical statement

Shared notation.

Standard number systems are $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$. Specialized notation and index ranges follow the cited source and the definitions below.

A convolutional arithmetic circuit combines local shared-weight operations with multiplicative pooling. A rectifier network uses ReLU activations; expressive power concerns functions representable within a stated size budget.

Record scope and qualifications.

The catalogue title is retained as metadata. Named certificates, contracts, bounds or frameworks in that title are not asserted as results of the original source extract. The training model, target family, resources, and comparison criterion must be specified by the cited source.

Source-record limitation: The target function family, training model, resource constraints, and meaning of advantage are unspecified.

Statement recorded in the supplied source.

Can the expressive power of convolutional arithmetic circuits be converted through training into a deep-learning architecture with a provable advantage over convolutional rectifier networks? [S2]

Source status.

The supplied catalogue labels this source record open; that metadata was checked against the supplied snapshot on 2026-10-11. The label is preserved for provenance and is not an independent verification of present open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

Turn the cited representational advantage into a provable advantage for a trainable deep-learning architecture.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30003757 (OWR-15999-005). Catalogue curation and metadata: CC BY 4.0. The source extract is retained; definitions, English summaries and qualifications are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Applied Harmonic Analysis and Data Processing $2019$, Oberwolfach Reports, DOI 10.4171/owr/2018/14, pp. 723--792 https://doi.org/10.4171/owr/2018/14.
• S3 Convolutional arithmetic circuits https://proceedings.mlr.press/v48/cohenb16.html.
• S4 ConvAC preprint https://arxiv.org/abs/1603.00162.
• S5 ConvAC expressivity https://arxiv.org/abs/1703.02065.
• Source-specific Oberwolfach Reports licences, including CC BY-SA 4.0 where applicable, are retained; see THIRD_PARTY_NOTICES.md.

Preparation and review.

The original source and UnsolvedMath contributors retain attribution for the source extract. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, scope notes and formatting. No new human mathematical authorship or independently verified solution is asserted. Permanent source ID 30003757 and code OWR-15999-005 checked against the complete supplied registry and current repository. Distinct upstream records, including repeated questions and broad or damaged extracts, are retained for complete coverage of the source CS category. A repeated record is not a new independent conjecture. Complete mathematical-equivalence and current-literature review has not been performed. Preparation and final review follow contribution prompts C and D, with source gaps disclosed. Structural and rendering checks do not establish a new theorem or open status.

Literature and context check

The convolutional-arithmetic-circuit discussion in OWR 14/2018, pp. 745--746, was read. It relates product pooling to tensor decompositions and explicitly separates expressive capacity from successful training. The following product-function experiment provides a small exact separation, a constructive approximation bound and a training obstruction. It is not a new comparison theorem for the source's full convolutional architecture families.

Research attempt: Exact expressiveness versus approximation and trainability

An exact representation boundary.

For $d\ge2$, the function $f(x)=\prod_{j=1}^d x_j$ on $[0,1]^d$ is computed by a binary tree of $d-1$ product operations, with balanced depth $\lceil\log_2d\rceil$ up to padding. It is therefore a natural elementary product-pooling computation. A finite network built only from affine maps, ReLU, maximum and average pooling is piecewise affine with finitely many pieces: affine maps preserve this property, a ReLU or maximum refines finitely many affine regions by finitely many linear inequalities, and compositions remain finite. On the diagonal $x_1=\cdots=x_d=t$, its restriction is piecewise affine on finitely many intervals. It cannot equal $t^d$ on $(0,1)$, whose second derivative is $d(d-1)t^{d-2}>0$. Thus exact representation separates these operations on this continuum domain.

That exact separation is not an approximation lower bound.

Interpolate $t^2$ linearly on the uniform grid $0,h,\ldots,mh=2$, $h=2/m$. On a grid interval $[a,b]$, the interpolation error is exactly $(t-a)(b-t)$, between zero and $h^2/4=1/m^2$. The interpolant has the ReLU representation \[ q_m(t)=h t+2h\sum_{j=1}^{m-1}\max(0,t-jh),\qquad 0\le t\le2. \] The slope starts at $h$ and increases by $2h$ at each knot, agreeing with the secant slopes of the square.

For $x,y\in[0,1]$, use $xy=((x+y)^2-x^2-y^2)/2$ and define \[ M_m(x,y)=\operatorname{clip}_{[0,1]} \left(\frac{q_m(x+y)-q_m(x)-q_m(y)}2\right). \] Clipping is itself $\max(0,z)-\max(0,z-1)$ and cannot increase the distance to a target in $[0,1]$. Therefore $|M_m(x,y)-xy|\le3/(2m^2)$. Compose these modules on the same binary tree. If child approximations have errors $e_1,e_2$ and all exact and approximate values lie in $[0,1]$, then \[ |ab-\widetilde a\widetilde b| \le|a-\widetilde a|+|b-\widetilde b|, \] so the root error is at most $(d-1)3/(2m^2)$ by induction over the tree. Choosing $m\ge\sqrt{3(d-1)/(2\epsilon)}$ yields uniform error at most $\epsilon$, with $O(dm)$ ReLU units and depth $O(\log d)$. The multiplication module can share coefficients between nodes. This is a constructive general ReLU approximation; it is not asserted to obey every exact channel, filter and pooling restriction of the source's comparison architecture. It does prove that the bare piecewise-affine argument alone cannot establish a superpolynomial approximate-representation gap.

Expressibility alone does not make gradient training fast.

Even this elementary arithmetic computation can have flat training dynamics. Put one shared scalar parameter $w$ at all $d$ leaves, so the output at the all-ones input is $w^d$, and train on target one with \[ L(w)=\tfrac12(w^d-1)^2,\qquad L'(w)=d w^{d-1}(w^d-1). \] The global loss is zero at $w=1$, but gradient descent started at $w=0$ never moves for $d\ge2$. More quantitatively, with a fixed step size $\eta>0$ and start $w_0=1/4$, before the first iterate reaching $1/2$ every increment is positive and at most $\eta d\,2^{-(d-1)}$. Thus the number of updates needed to reach $1/2$, if it is ever reached, is at least \[ \frac{1/4}{\eta d\,2^{-(d-1)}}=\frac{2^{d-3}}{\eta d}. \] The bound counts all pre-crossing updates, including the final one, so it remains valid if that step overshoots. For a step size bounded independently of $d$, this is exponentially many iterations in this parameterization. It is not a lower bound for all optimizers, initializations or reparameterizations; it identifies a concrete failure of the inference from a short product circuit to efficient gradient training.

Verification and adversarial audit

The piecewise-affine induction and diagonal restriction prove only exact nonrepresentation. The square-interpolation error, explicit ReLU formula, clipping contraction and tree error accumulation were checked to provide an actual opposing approximation construction. The training derivative and first-crossing bound are elementary exact calculations with the step-size dependence retained. No benchmark or full convolutional-network training experiment was run.

Audit corrections.

Did not use exact nonrepresentation as an approximate lower bound. Added an explicit polynomial-size ReLU approximation and a quantitative product-parameter training obstruction; neither is claimed to classify all convolutional architectures.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

No trained convolutional-arithmetic architecture with a full statistical or computational advantage over the source's rectifier class is established. Exact representation, approximation with a specified tolerance, and optimization time are distinct. The first missing steps are an exact resource-matched architecture comparison and a training/generalization theorem under an identified data model.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The calculations below the preserved source statement investigate a concrete route, but establish no substantiated new progress toward the entire original target. Known special cases and failed sufficient conditions are not credited as a solution.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

• https://ems.press/content/serial-article-files/46736 (consulted 2026-10-11).

Model and contributor disclosure

OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration, repository-format review, and written-proof review of this attempt; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Unresolved as a new research contribution. This is a concrete route investigation, not a claim of new complete resolution or a current-status certification. A known answer reproduced for context does not become a new contribution. The catalogue's source-status label is preserved; this attempt status does not assert that a source-labelled solved question is open.