1Cademy - Counting the auxiliary substitution and restriction pairs

Learn Before

Recovering a local expansion from fixed substitutions and restricted sums
Reading the parameter bounds as asymptotic statements

Concept

Counting the auxiliary substitution and restriction pairs

For truncation order q, the recovery procedure considers U subset E subset {1,...,n} with |E|<=q. There are C_q=sum_{s=0}^{min(q,n)} 2^s*binom(n,s) pairs: choose E of size s, then any of its 2^s subsets U. Thus C_0=1 and C_q=3^n if q>=n. For 0<eta<=1, eta^q*C_q<=(1+2eta)^n, since eta^q<=eta^s for every retained s. If q=O(nR/Q) and 0<R/Q<1, choose eta=R/Q; taking logs gives log2 C_q=O(n*(R/Q)*log2(2Q/R)). This bound needs the stated order for q, not just small factor scopes.

Updated 2026-11-07

Contributors are:

Who are from:

References