By OpenAISourceGitHub

Manuscripts from openai/math

Fork
Clone
git clone https://openversions.com/git/index/openai-math.git
Cite
Version link
https://openversions.com/index/openai-math/commit/dfd8c46870b48511e697cbb43a3c8c91d375fa2f
Version identifier (commit hash)
dfd8c46870b48511e697cbb43a3c8c91d375fa2f

Fork to create your own copy with credit to the source. Clone to get a Git copy on your computer.

All papers

Claims

Findings

From partial permutation information to Fourier bounds

If n tends to infinity through multiples of eight, and the images of a uniformly chosen 7n/8 labels under a probability law on S_n approach the uniform injection law in average total variation while the sign mean tends to zero, then the product of two independent permutations with the given law converges to uniform on S_n in total variation.

For any partition of X into b nonempty sets M_1, ..., M_b with H_i = Sym(M_i), if a nonnegative measure f on G = Sym(X) of mass at most 1 satisfies f(gH_i) <= B/[G:H_i] for all g and i, then for every u > 0 and every irreducible representation rho of degree D, ||\widehat{f}(\rho)||_{\mathrm{HS}}^2 \le b B C_u D−1+(u+2)/bD^{-1+(u+2)/b} and independently ||\widehat{f}(\rho)||_{\mathrm{op}}^2 \le b B C_u D−1+(u+2)/bD^{-1+(u+2)/b}, with no restriction on block sizes or multiplicities.

For every u > 0, the supremum C_u = \sup_{m \ge 1} \sum_{\lambda \vdash m} D_\lambda^{-u} is finite, and Z_u(n) = \sum_{\lambda \vdash n, \lambda \notin \{(n), (1^n)\}} D_\lambda^{-u} \to 0 as n \to \infty.

For every irreducible complex representation of S_n of degree D, there exist a subgroup J <= S_n and a character \chi : J \to \{1, -1\} occurring in its restriction such that [S_n : J] \le D1024D^{1024}, which yields the character-projection transfer bound ||\widehat{f}(\rho)||_{\mathrm{HS}}^2 \le B z b C_1 D−1+1026/bD^{-1+1026/b} under disjoint-block coset caps.

For disjoint block subgroups H_1, ..., H_b, if alpha >= 0 has mass a <= 1 with left-coset caps alpha(H_i g) <= B_L / [S_n : H_i] and beta >= 0 has mass c <= 1 with right-coset caps beta(g H_i) <= B_R / [S_n : H_i], then D_\lambda ||\widehat{\beta}(\lambda)\widehat{\alpha}(\lambda)||_{\mathrm{HS}}^2 \le B_L B_R a c K_\lambda^2 D_\lambda^{-1+4/b}, where K_\lambda is the number of distinct joint restriction types.

For a sequence of doubly stochastic H-equivariant kernels K on Bij(A, V) with 16 blocks of sizes m_i -> \infty, if the 16 quotient kernels q_i approach uniform in average total variation and the truncated sign-multiplicity operators T_i^{\mathrm{sgn}} satisfy ||T_i^{\mathrm{sgn}}||_{\mathrm{HS}}^2 \to 0, then K16K^{16} mixes in average row total variation (and worst-start total variation if K is equivariant under a transitive group).

Under 1024-omitted-set or 256-omitted-set averaged marginal total-variation hypotheses (and o(1) sign mean), conditioning on the event that at least 7/8 of the omitted sets have coset mass at most twice uniform yields a nearby law \nu_n with ||\widehat{\nu}_n(\rho)||_{\mathrm{op}} \le C D−1/4D^{-1/4} (for q=1024, giving 8-convolution mixing) or ||\widehat{\nu}_n(\rho)||_{\mathrm{op}} \le C D−1/8D^{-1/8} (for q=256, giving 32-convolution mixing).

If every probability law \sigma supported on a common event \mathcal{G} of probability a > 0 satisfies the relative-entropy comparison D(\sigma || \mathbb{P}) \ge \mathbb{E}_{|X|=n-n/128} D(\sigma_X || U_X) - n−2n^{-2}, then for every irreducible \rho of degree D and unit vectors u, z, \mathbb{P}\{\mathcal{G}, |\langle z, \rho(g)u\rangle| \ge D−1/8D^{-1/8}\} \le C D−1/256D^{-1/256}, and the conditioned law \eta satisfies ||\widehat{\eta}(\rho)||_{\mathrm{op}} \le D−1/8D^{-1/8} + (C/a) D−1/256D^{-1/256}.

If a probability \mu on S_n (n even) satisfies the signed-palette coset caps \mu(xH) \le [S_n:H]^{-1} \exp\{v \mathcal{H}(p) + \varepsilon_n\} for every palette on either half, then for all sufficiently large n and every nontrivial nonsign \lambda \vdash n, ||\widehat{\mu}(\lambda)||_{\mathrm{HS}}^2 \le D_\lambda^{-1/3} and ||\widehat{\mu}(\lambda)||_{\mathrm{op}} \le D_\lambda^{-1/6}; with |\widehat{\mu}(\mathrm{sgn})| = o(1), ||\mu^{*4} - USnU_{S_n}||_{\mathrm{TV}} = o(1).

If a probability \mu on S_n satisfies a weak 16-block relative-entropy bound E_n <= C(1 + \log n)^4 and an independent probability K satisfies ||\widehat{K}(\lambda)||_{\mathrm{op}} \le n−k/10n^{-k/10} for 1 <= k = n - \lambda_1 <= n1/20n^{1/20} and \widehat{K}(\lambda) = 0 for \lambda_1' > n/2, then ||\mu^{*12} * K∗40K^{*40} - USnU_{S_n}||_{\mathrm{TV}} = o(1).

In the conditional-product setting on V = A \sqcup C with |A|=|C|=h, if \xi has inverse-image caps on A and C, and conditional on an environment Z the half-permutations \nu_A^z, \nu_C^z have buffer-complement image caps for L >= 2 C_0 buffers (C_0 = 2,000,000), then \theta = \mathbb{E}_Z[\delta_{t_Z} * (\nu_A^Z \otimes \nu_C^Z)] * \xi satisfies ||\widehat{\theta}(\lambda)||_{\mathrm{op}} \le \sqrt{22} D_\lambda^{-1/40} for all sufficiently large h and all D_\lambda > 1.

Methods

Orbit-span transfer via least-index tensor-type assignment and Schur averaging over group translates.

Source excerpts

“Assign its whole isotypic space to the least index i for which dim τi ≤ D1/b. Group the assigned spaces to obtain Vρ = E1 ⊕ · · · ⊕ Eb.” · Show in paper

“Indeed EU ρ(g)Πiρ(g) ∗ commutes with ρ(G) and has trace dim Wi , so Schur’s lemma identifies it as (dim Wi/D)I.” · Show in paper

Central-idempotent isotypic projection and cosetwise Plancherel estimation.

Source excerpts

“For an irreducible H-type τ of degree a, define the mass function eH,τ (h) = a |H| χτ (h) (h ∈ H), eH,τ = 0 off H. Character orthogonality shows that ebH,τ (ρ) is the orthogonal projection Pρ,H,τ onto the full τ -isotypic subspace in ρ|H.” · Show in paper

Successive and simultaneous coset trimming, and entropy clipping, to construct a common subprobability satisfying multiple coset caps.

Source excerpts

“Process the subgroup coset systems successively. Within each coset whose current mass exceeds its uniform mass, multiply all current point masses by the ratio of the cap to the current mass.” · Show in paper

“For each i let pi be the density of wHi relative to UG/Hi . Restrict w to those g for which pi(gHi) ≤ e t for every i, and call the result v.” · Show in paper

One-dimensional subgroup character construction via arm-leg row-column assignment and longest-line peeling.

Source excerpts

“Assign a box to its row when its arm is at least its leg, and to its column otherwise.” · Show in paper

“Remove the longer of the first row and first column of the current diagram.” · Show in paper

Polynomial-size signed tabloid embedding and Littlewood-Richardson multiplicity bounding for conditional half-products.

Source excerpts

“Frobenius reciprocity now places Vλ in IndSm J χ. Its coset basis is indexed by the ordered set partitions of sizes s1, . . . , sr, and each group element permutes this basis with signs because χ takes values in {1, −1}.” · Show in paper