Answer: All allocation and payment functions converge uniformly. For \(m=1\), their limits are exactly computable in polynomial time as continuous piecewise affine functions with rational coefficients.
Theorem D.2 — class: algorithmic
Given a rational distribution μ over advertiser types \(t=(v_t,B_t)\), a maximum per-advertiser supply \(S\), and ε>0, take each replication factor \(q\) for which \(qμ_t\) is integral. Run ACA on \(qμ_t\) bidders of each type with total supply \(qs\), using one uniformly random priority order to break equal-value ties and reusing it across \(s\in[0,S]\). For each type, let \(X_{t,q}(s)\) and \(P_{t,q}(s)\) be its expected average per-bidder allocation and payment. Do these curves converge uniformly as \(q\to\infty\), and can an algorithm compute ε-approximations to the limiting curves uniformly over \(s\in[0,S]\) in time polynomial in support size τ, input bit length \(L\), and \(\log(1/\epsilon)\), independent of \(q\)?
A society is given by its support: the list of \(\tau\) distinct advertiser types \(t=(v_t,B_t)\) with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Values and public budgets are positive binary rationals; there is one divisible good, so \(m=1\). Let \(S>0\) be rational, \(\epsilon=2^{-k}\) with positive integer \(k\), and \(L\) the bit length of the society and \(S\). Advertisers have constant marginal values and no allocation caps; \(S\) bounds total supply per bidder.
For a finite population and supply \(a\), define the Adaptive Clinching Auction (ACA) as follows. At ascending price \(p\), initialize allocations \(x_i(0)=0\) and remaining budgets \(b_i(0)=B_i\); write \(R=a-\sum_i x_i\), \(A=\{i:v_i>p\}\), and \(C=\{i\in A:R=\sum_{j\in A\setminus\{i\}}b_j/p\}\).
Between value events, for \(p>0\), use right derivatives \(x_i'=R/p\), \(b_i'=-R\) for \(i\in C\), and zero derivatives otherwise. States are continuous between events and right-continuous at events.
At price \(u\), remove bidders of value \(u\) one at a time in priority order. After each removal, with remaining set \(A\), simultaneously allocate \(\delta_i=\max\{0,R-\sum_{j\in A\setminus\{i\}}b_j/u\}\) and charge \(u\delta_i\) to each \(i\in A\), then update budgets and residual supply before the next removal. Stop when supply is exhausted; zero supply gives zero allocations and payments. Final payments are \(\pi_i=B_i-b_i\).
For each integer \(q\ge2\) with every \(q\mu_t\) integral, run ACA on \(q\mu_t\) bidders of each type with supply \(qs\). Draw one uniformly random priority permutation for that population and reuse it for all \(s\in[0,S]\). Define \(X_{t,q}(s)=\mathbb E[\sum_{i:t_i=t}x_i/(q\mu_t)]\) and \(P_{t,q}(s)=\mathbb E[\sum_{i:t_i=t}\pi_i/(q\mu_t)]\).
Uniform approximation means finite descriptions of functions \(\widehat X_t,\widehat P_t\) satisfying \(\max_t\sup_{s\in[0,S]}\max\{|\widehat X_t(s)-X_t(s)|,|\widehat P_t(s)-P_t(s)|\}\le\epsilon\); their rational-query evaluators must run in time polynomial in \(m,\tau,L,k\) and the query bit length.
Do all \(X_{t,q},P_{t,q}\) converge uniformly on \([0,S]\) along the admissible replication factors?
If they do, is computing uniform \(\epsilon\)-approximations to their limits possible in time polynomial in \(m,\tau,L,\log(1/\epsilon)\), independent of \(q\), or is this computation NP-hard?
For finite populations, Goel, Mirrokni and Paes Leme establish an ACA algorithm using \(\widetilde O(n)\) arithmetic operations; this is not a bit-complexity bound. [Source](https://www.cs.cornell.edu/~renatoppl/papers/online-clinching-soda13.pdf)
No result settling this precise uniform replication-limit computation was identified in the literature search.
All the expected allocation and payment functions converge uniformly on the specified supply interval. Their limits have exact descriptions as continuous piecewise affine functions with rational coefficients, computable in polynomial time.
The argument uses the known supply-monotonicity theorem for finite ACA populations. It does not use the finite-population arithmetic-operation bound as a bit-complexity bound.
Let the distinct values in the support be \(u_1<\cdots<u_d\). Define
\(E_j=\sum_{t:v_t=u_j}\mu_tB_t,\qquad W_j=\sum_{t:v_t\ge u_j}\mu_tB_t,\qquad W_{d+1}=0.\)
Thus \(E_j=W_j-W_{j+1}>0\). The following formulas cover every nonnegative supply.
Clearing at a value. If
\(\displaystyle \frac{W_{j+1}}{u_j}\le s\le\frac{W_j}{u_j},\)
put
\(\displaystyle r_j(s)=\frac{u_js-W_{j+1}}{E_j}.\)
Here \(r_j(s)\in[0,1]\). The limits are
\(\displaystyle X_t(s)= \begin{cases} B_t/u_j,&v_t>u_j,\\ r_j(s)B_t/u_j,&v_t=u_j,\\ 0,&v_t<u_j, \end{cases} \qquad P_t(s)= \begin{cases} B_t,&v_t>u_j,\\ r_j(s)B_t,&v_t=u_j,\\ 0,&v_t<u_j. \end{cases}\)
Clearing between consecutive values. If
\(\displaystyle \frac{W_{j+1}}{u_{j+1}}<s<\frac{W_{j+1}}{u_j},\qquad 1\le j<d,\)
put \(p_*=W_{j+1}/s\), so \(u_j<p_*<u_{j+1}\). Then
\(\displaystyle X_t(s)= \begin{cases} B_ts/W_{j+1},&v_t\ge u_{j+1},\\ 0,&v_t\le u_j, \end{cases} \qquad P_t(s)= \begin{cases} B_t,&v_t\ge u_{j+1},\\ 0,&v_t\le u_j. \end{cases}\)
Finally, for \(s>W_1/u_1\),
\(\displaystyle X_t(s)=B_ts/W_1,\qquad P_t(s)=B_t.\)
The first formula includes \(s=0\), where all outcomes are zero.
Each displayed function is piecewise affine with rational coefficients. At the endpoints of a value interval, \(r_j=0\) or \(r_j=1\), and the adjacent formulas agree: substituting \(s=W/u_j\) into an adjacent gap formula gives allocation \(B_t/u_j\) for its active types. Consequently, every limit function is continuous.
We now prove that these are the replication limits.
Fix a finite population, its priority order, and positive supply. While supply remains, write
\(T(p)=\sum_{i\in A}b_i(p),\qquad D(p)=T(p)-pR(p),\qquad M(p)=\max_{i\in A}b_i(p).\)
During sequential removals at a value event, the active set means the set remaining after the removals performed so far.
We establish the invariant \(D\ge M\).
Between value events, if \(c=|C|\), the stated derivatives give
\(\displaystyle T'=-cR,\qquad R'=-\frac{cR}{p},\qquad D'=T'-R-pR'=-R.\)
The defining equality for a clinching bidder is exactly \(b_i=D\). Hence, whenever \(D\ge M\), either no bidder clinches, or \(D=M\) and precisely the bidders with maximum remaining budget clinch.
If \(D>M\), budgets and residual supply stay constant until \(D\) reaches \(M\), or a value event occurs. When \(D=M\), every maximum-budget bidder has budget derivative \(-R=D'\). Their budgets therefore remain equal to \(D\). Other bidders join when this decreasing common budget reaches theirs. This preserves \(D\ge M\) between events.
At a value event of price \(u\), suppose bidder \(j\) is removed. Immediately after removal and before allocation, let
\(\widetilde D=D-b_j.\)
Since the invariant held before removal, \(\widetilde D\ge0\). The simultaneous charge to each remaining bidder is
\(\displaystyle u\delta_i=(b_i-\widetilde D)_+.\)
Thus the new budget is \(\min\{b_i,\widetilde D\}\). Subtracting the total charge from both \(T\) and \(uR\) leaves their difference unchanged, so the new deficit is still \(\widetilde D\). Every remaining budget is at most this deficit, establishing the invariant after the update.
The update is feasible. Charges do not exceed budgets. If any charge is positive, some updated budget equals \(\widetilde D\), so their sum is at least \(\widetilde D\); consequently the updated residual supply is nonnegative. If \(\widetilde D=0\), all remaining budgets are charged completely and residual supply becomes zero.
Two consequences will be used:
Also, every allocated increment is charged at its current price: between events, \(-b_i'=p x_i'\), and at events the charge is \(u\delta_i\).
Fix a supply whose candidate clearing price \(p_*\) lies strictly between consecutive values, or strictly below \(u_1\).
Let \(H\) be the total budget mass of types with \(v_t>p_*\). Then
\(p_*=H/s.\)
Let \(M\) be the largest original budget among these types, and let \(\mu_{\min}=\min_t\mu_t>0\).
For sufficiently large admissible replication factors, no allocation occurs at earlier value events. To verify this, let \(\ell\) be the largest support value below \(p_*\), or zero if none exists. Throughout prices at most \(\ell\), including intermediate removals, the remaining original budgets include those of all types above \(p_*\). In the absence of allocations,
\(\displaystyle D\ge q(H-\ell s).\)
Because \(\ell<p_*=H/s\), this lower bound eventually exceeds every bidder’s budget. Therefore neither continuous clinching nor an event allocation can occur there.
After these lower-valued bidders have departed, the first clinching price is
\(\displaystyle p_{0,q}=\frac{qH-M}{qs}.\)
For sufficiently large replication factors it lies in the same value-free interval as \(p_*\), and \(p_{0,q}\to p_*\).
Choose \(p_1>p_*\) before the next support value. At least one entire maximum-budget type enters the clinching set at \(p_{0,q}\), contributing at least \(q\mu_{\min}\) bidders. They remain clinching up to \(p_1\). Integrating the residual-supply differential inequality gives
\(\displaystyle R(p_1)\le qs\left(\frac{p_{0,q}}{p_1}\right)^{q\mu_{\min}}.\)
The ratio tends to \(p_*/p_1<1\), so \(R(p_1)/q\to0\). Because clinching remains active,
\(\displaystyle T(p_1)=p_1R(p_1)+M(p_1)\le p_1R(p_1)+B_{\max},\)
where \(B_{\max}=\max_tB_t\). Hence \(T(p_1)/q\to0\).
For any active type, its average expenditure by \(p_1\) is at least
\(\displaystyle B_t-\frac{T(p_1)}{q\mu_t}.\)
Final payments lie between this quantity and \(B_t\). Thus their averages converge to \(B_t\), independently of the priority order.
All allocations occur at prices at least \(p_{0,q}\). Expenditure incurred by \(p_1\) purchases goods at prices at most \(p_1\). Consequently the final average allocation of an active type lies between
\(\displaystyle \frac{B_t-T(p_1)/(q\mu_t)}{p_1}\)
and \(B_t/p_{0,q}\). Taking limits and then letting \(p_1\) decrease to \(p_*\) proves convergence to \(B_t/p_*\).
Lower-valued types departed before any allocation and receive zero. This proves the claimed limits throughout the open gap intervals.
Fix a value \(u=u_j\), and abbreviate
\(H=W_{j+1},\qquad E=E_j.\)
Assume initially that
\(H<us<H+E.\)
The strict upper inequality implies that, for sufficiently large replication factors, no allocation occurs before this value event. Indeed, before any removal at \(u\), the deficit in the absence of allocation is at least \(q(H+E-us)\), which eventually exceeds every individual budget.
Let
\(\displaystyle N=q\sum_{t:v_t=u}\mu_t,\qquad D_0=q(H+E-us).\)
The relative priority order of these tied bidders is a uniformly random permutation.
For a prefix of length \(a\) in that permutation, let \(T_a\) be its sum of original budgets. Let \(\lambda\) be the number of removals up to and including the first removal that causes a positive allocation.
Before this allocation, all remaining budgets are original budgets and residual supply is \(qs\). Immediately after its triggering removal, the deficit is \(D_0-T_\lambda\). The invariant and the occurrence of a positive allocation imply
\(\displaystyle 0\le D_0-T_\lambda<B_{\max}.\)
Such a triggering removal must exist: removing all tied bidders without allocation would give deficit \(q(H-us)<0\), contradicting the invariant.
Define the removed fraction
\(\displaystyle d=\frac{H+E-us}{E}\in(0,1).\)
We claim that \(\lambda/N\to d\) in probability.
For any fixed \(\alpha\in[0,1]\), set \(a=\lfloor\alpha N\rfloor\). Sampling without replacement gives
\(\displaystyle \mathbb E[T_a]=\frac{a}{N}qE,\qquad \operatorname{Var}(T_a)\le NB_{\max}^2.\)
For completeness, if the population variance of the tied budgets is \(\sigma^2\), distinct positions in the random permutation have covariance \(-\sigma^2/(N-1)\). Summing variances and covariances yields
\(\displaystyle \operatorname{Var}(T_a)=\frac{a(N-a)}{N-1}\sigma^2\le NB_{\max}^2.\)
Therefore \(T_{\lfloor\alpha N\rfloor}/q\to\alpha E\) in probability.
Choose any positive \(\eta<\min\{d,1-d\}\). With probability tending to one,
\(\displaystyle T_{\lfloor(d-\eta)N\rfloor}<D_0-B_{\max}, \qquad T_{\lfloor(d+\eta)N\rfloor}>D_0.\)
Together with the bound on \(T_\lambda\) and positivity of budgets, these inequalities place \(\lambda\) between those two prefix lengths. This proves the claim.
Let \(K_t(a)\) count type \(t\) in a prefix of length \(a\). Applying the same sampling calculation to type indicators gives
\(\displaystyle \frac{K_t(\lfloor dN\rfloor)}{q\mu_t}\to d\)
in probability. Since
\(\displaystyle |K_t(\lambda)-K_t(\lfloor dN\rfloor)| \le|\lambda-\lfloor dN\rfloor|,\)
we also obtain
\(\displaystyle \frac{K_t(\lambda)}{q\mu_t}\to d.\)
These fractions are bounded, so their expectations converge as well.
Put \(B_{\min}=\min_tB_t>0\). After the first positive allocation, budgets are clipped at the current deficit, which is less than \(B_{\max}\).
If the current deficit exceeds \(B_{\min}\), the next tied bidder has remaining budget at least \(B_{\min}\), so its removal decreases the deficit by at least that amount. If the deficit is at most \(B_{\min}\), the next tied bidder’s remaining budget equals the deficit; its removal makes the deficit zero and exhausts supply.
Thus at most
\(\displaystyle K=\left\lceil B_{\max}/B_{\min}\right\rceil+1\)
further removals are needed.
There are enough tied bidders to perform these removals for all sufficiently large replication factors. At the first allocation, their remaining original budget sum is at least
\(\displaystyle qE-D_0=q(us-H)>0.\)
Their number is therefore at least \(q(us-H)/B_{\max}\), which grows without bound.
When the deficit reaches zero, every surviving bidder spends its remaining budget. Consequently:
For a tied type this gives the deterministic bound
\(\displaystyle 0\le B_t\bigl(q\mu_t-K_t(\lambda)\bigr) -\sum_{i:t_i=t}\pi_i \le KB_{\max}. \)
Taking expectations and dividing by \(q\mu_t\) proves
\(\displaystyle P_{t,q}(s)\to(1-d)B_t =\frac{us-H}{E}B_t.\)
All allocation occurs at price \(u\), so allocation equals payment divided by \(u\). This establishes the claimed tie formulas on their open intervals.
We use the following established finite-population result: with public budgets, a divisible homogeneous good, and a fixed order for resolving equal values, each bidder’s final ACA allocation and payment is nondecreasing in supply. This is Theorem 4.1 together with the repeated-value extension in Appendix C of [Goel, Mirrokni and Paes Leme](https://www.cs.cornell.edu/~renatoppl/papers/online-clinching-soda13.pdf).
Its hypotheses match this task: values are constant, budgets are public, and feasible allocations are nonnegative with total allocation bounded by supply. Relabeling bidders makes any fixed priority order the order used in Appendix C. The question’s reuse of a permutation across supplies permits this theorem to be applied before taking expectations. Thus every \(X_{t,q}\) and \(P_{t,q}\) is nondecreasing in \(s\).
Temporarily extend these functions to all nonnegative supplies by running the same finite auction. The preceding arguments prove pointwise convergence except at finitely many positive breakpoints. At any such breakpoint \(s_0\), choose nearby non-breakpoints \(a<s_0<b\). For either outcome coordinate \(f_q\),
\(f_q(a)\le f_q(s_0)\le f_q(b).\)
Taking limits and then letting \(a\) and \(b\) approach \(s_0\), continuity of the candidate limit proves convergence there. At zero, convergence is immediate because every finite outcome is zero. Hence convergence holds at every point.
We now justify uniformity without assuming monotonicity in the replication factor.
Let \(f_q\) be any one of the outcome coordinates, and let \(f\) be its continuous limit on \([0,S]\). For any \(\eta>0\), continuity provides a finite partition
\(0=s_0<s_1<\cdots<s_h=S\)
such that \(f(s_{a+1})-f(s_a)<\eta\) on every partition interval. Pointwise convergence at the finitely many partition points gives, for sufficiently large admissible replication factors,
\(\displaystyle \max_a|f_q(s_a)-f(s_a)|<\eta.\)
For \(s_a\le s\le s_{a+1}\), monotonicity bounds \(f_q(s)\) between its two endpoint values. It follows that
\(\displaystyle |f_q(s)-f(s)|<2\eta.\)
Thus convergence is uniform. There are only finitely many types and two coordinates per type, so
\(\displaystyle \max_t\sup_{s\in[0,S]} \max\{|X_{t,q}(s)-X_t(s)|,\ |P_{t,q}(s)-P_t(s)|\} \longrightarrow0. \)
An exact representation can be constructed as follows:
There are at most \(d\le\tau\) distinct values and a linear number of intervals. Even storing separate formulas for every type on every interval uses only polynomial space.
Every coefficient and breakpoint is obtained by polynomially many rational additions, multiplications, and divisions from the input. Their numerator and denominator bit lengths remain polynomial in \(\tau\) and \(L\): products add bit lengths, and sums can be formed over products of the input denominators. Exact rational comparisons, arithmetic, and sorting therefore take polynomial bit time.
At a rational query, an evaluator locates the relevant interval by rational comparisons and evaluates its affine formula. Its running time and output bit length are polynomial in \(\tau\), \(L\), and the query bit length.
Set \(\widehat X_t=X_t\) and \(\widehat P_t=P_t\) using these exact descriptions. Their approximation error is zero, so they satisfy every requested tolerance. Construction is polynomial in the required parameters, independent of the replication factor, and requires no numerical simulation of finite ACA populations.
⟨structured verdict parsed — rendered above⟩
The argument establishes the requested uniform replication limits and polynomial-time computation in substance. I found no false central step or major gap. Two routine details should be made explicit; the appropriate classification is proved with minor gaps.
The value intervals and intervening gap intervals cover every positive supply, together with the final interval above \(W_1/u_1\). Positivity of masses and budgets ensures \(E_j>0\), so the divisions defining \(r_j\) are valid. Every denominator in a gap formula is also positive because \(j<d\).
At each positive breakpoint, the adjacent allocation and payment formulas agree. At zero, the formula for the highest value gives zero for every type. Thus the claimed continuity is correct, including when there is only one distinct value.
The formulas are piecewise affine with rational coefficients. The auxiliary expression \(p_*=W_{j+1}/s\) does not introduce a nonaffine outcome formula: allocations on that interval are explicitly linear in \(s\), and payments are constant.
The calculations
\[
T'=-cR,\qquad R'=-cR/p,\qquad D'=-R
\]
are correct. The clinching equality is equivalent to \(b_i=D\). Consequently, under \(D\ge M\), clinching bidders are exactly the maximum-budget bidders when equality holds.
The preservation argument between events is consistent: maximum-budget bidders have the same derivative as \(D\), and additional bidders join when the common remaining budget reaches theirs.
At a removal, the identities
\[
\widetilde D=D-b_j,\qquad
u\delta_i=(b_i-\widetilde D)_+
\]
are correct. The resulting budget clipping and preservation of the deficit follow from the simultaneous update. The feasibility argument correctly establishes nonnegative remaining budgets and nonnegative residual supply.
Minor issue: The invariant’s initial base case is not explicitly checked. Preservation alone does not formally establish an invariant.
Minimum clarification: State that \(D\ge M\) holds initially for the task’s positive-budget population, and that maximum-budget notation is used only while the auction remains active.
The assertion about original-budget clipping is consistent with the described evolution: continuous spending affects the current maximum budgets, and event updates clip budgets at a decreasing deficit. No additional structural lemma is needed here.
The lower bound \(q(H-\ell s)\) is strictly positive before the proposed clearing interval and eventually exceeds every individual original budget. Applied up to a hypothetical first allocation, this rules out earlier continuous clinching and event allocations. The argument is therefore not circular.
The first clinching price
\[
p_{0,q}=\frac{qH-M}{qs}
\]
is correct and converges to \(p_*\). For sufficiently large admissible factors, it is positive and lies in the intended interval.
An entire maximum-budget type starts clinching, so the stated lower bound on the clinching-set size is valid. Its persistence gives the displayed exponential residual-supply bound. The subsequent bound on \(T(p_1)\) correctly uses \(D=M\) during clinching.
The payment bounds imply convergence of each active type’s average payment to its original budget. The allocation bounds correctly use the prices paid for allocated increments. Taking the limit in the replication factor first, and then letting \(p_1\) approach \(p_*\), establishes the claimed allocation limit.
These bounds are independent of priority order, so they also justify convergence of the expected outcomes. The same argument covers clearing strictly below the smallest value, including the entire final supply interval.
The strict inequalities \(H<us<H+E\) correctly provide both a positive initial deficit and enough supply to force an allocation during the tied event. The absence of earlier allocation is justified by the positive budget-mass margin.
The bound
\[
0\le D_0-T_\lambda<B_{\max}
\]
is correct: the triggering bidder is removed before the allocation, and the surviving bidder that receives a positive allocation has budget exceeding the new deficit.
The random-prefix calculation correctly identifies the threshold fraction \(d\). Monotonicity of prefix budget sums and the two concentration bounds justify convergence of \(\lambda/N\). The comparison between type counts at the random prefix and at the deterministic prefix is valid. Boundedness then justifies convergence of their expectations.
Minor issue: The displayed variance identity contains \(N-1\) in the denominator, although a small admissible population can have \(N=1\). Also, “population variance” should have its normalization specified for the exact identity.
Minimum clarification: Restrict this calculation to sufficiently large replication factors with \(N\ge2\), and define the variance using normalization by \(N\). This does not affect the limiting argument.
The bounded-removal argument is sound. After clipping, each further removed tied bidder either reduces the deficit by at least \(B_{\min}\), or reduces it to zero. The bound \(K\) is conservative but valid. The lower bound on the number of remaining tied bidders ensures that these removals are available for sufficiently large populations.
The deterministic payment-error bound correctly accounts for the first removed prefix and at most \(K\) later exceptional bidders. Dividing by the type population yields the proposed expected-payment limit. Since all allocation in this case occurs at price \(u\), the allocation conclusion follows.
Although \(K\) can be large relative to its binary description, it is used only in a convergence proof. It is not an iteration count in the proposed computation algorithm.
The cited result was checked. Theorem 4.1 gives coordinatewise monotonicity of both allocations and payments in supply for public-budget, constant-value bidders with a divisible good. Appendix C extends the mechanism to repeated values by ordered sequential removals and explains the extension of the proof. These are the hypotheses and tie treatment invoked here. [Goel, Mirrokni and Paes Leme, Theorem 4.1 and Appendix C](https://www.cs.cornell.edu/~renatoppl/papers/online-clinching-soda13.pdf)
Relabeling bidders accommodates any fixed priority order. Taking type averages and expectations preserves monotonicity. Thus the theorem application is justified.
The squeezing argument at positive breakpoints is valid because convergence has already been established on both neighboring open intervals and the candidate functions are continuous. Extending the finite-auction functions beyond \(S\) legitimately supplies a right-hand comparison when \(S\) itself is a breakpoint.
The finite-partition proof of uniform convergence is correct. It uses monotonicity in supply, not monotonicity in the replication factor. Pointwise convergence at finitely many partition points gives a common sufficiently large admissible factor, and endpoint bounds control every intervening supply.
Taking the maximum over finitely many types and the two outcome coordinates preserves convergence to zero. This establishes exactly the uniformity requested by the task.
The representation has a linear number of supply intervals and at most quadratically many type-specific affine formulas. The coefficients are built from budget-mass sums, input values, and their rational products and quotients. For these explicit expressions, numerator and denominator bit lengths remain polynomial in the input length.
Exact sorting, breakpoint comparisons, and affine evaluation therefore have polynomial bit complexity, including dependence on the rational query length. Restriction to the requested supply interval introduces no difficulty.
Using the exact descriptions gives zero approximation error for every requested tolerance. The construction is independent of the replication factor and does not rely on the finite-population arithmetic-operation bound.
Accordingly, the output resolves both questions: uniform convergence holds, and the limit functions admit polynomial-time exact computation. The two identified omissions require only routine exposition, not new mathematics.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.