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

Strong Ulam Stability Characterizes Amenability

A countable discrete group is strongly Ulam stable if and only if it is amenable.

For every nonamenable countable discrete group GG and every δ>0\delta > 0, there exists a separable Hilbert space HH and a normalized map μ:G→U(H)\mu : G \to \mathcal{U}(H) with def⁡(μ)<δ\operatorname{def}(\mu) < \delta such that sup⁡g∈G∥μ(g)−ρ(g)∥>110\sup_{g \in G} \|\mu(g) - \rho(g)\| > \frac{1}{10} for every unitary representation ρ:G→U(H)\rho : G \to \mathcal{U}(H).

For every nonamenable discrete group GG, every integer N≥1N \ge 1, and every 0<β<10 < \beta < 1, there exist finite nonempty sets X1,…,XN\mathcal{X}_1, \dots, \mathcal{X}_N and Y0,…,YN−1\mathcal{Y}_0, \dots, \mathcal{Y}_{N-1} and maps sk:Xk×Yk−1→Gs_k : \mathcal{X}_k \times \mathcal{Y}_{k-1} \to G and bk:G×Xk×Yk−1→{E,F}b_k : G \times \mathcal{X}_k \times \mathcal{Y}_{k-1} \to \{\mathrm{E}, \mathrm{F}\} satisfying compatibility (F1), departure sparsity of F\mathrm{F} (F2), and arrival sparsity of E\mathrm{E} (F3), with alphabet cardinalities independently enlargeable to be arbitrarily large and divisible by any prescribed positive integer.

For every 0<η<1/40 < \eta < 1/4 there is 0<β0<1/160 < \beta_0 < 1/16 such that if 0<β≤β00 < \beta \le \beta_0, then for every sufficiently large integer mm there are unit vectors (ax)x∈X(a_x)_{x \in X} in Rm\mathbb{R}^m with ∣X∣=2m|X| = 2m and signs f(x)∈{1,−1}f(x) \in \{1, -1\} such that the vectors with either sign form an orthonormal basis (so ∑x∈Xf(x)axax∗=0\sum_{x \in X} f(x) a_x a_x^* = 0) and every subset S⊆XS \subseteq X with ∣S∣≤4β∣X∣|S| \le 4\beta|X| has synthesis map FSF_S satisfying ∥FS∗FS−I∥≤η\|F_S^* F_S - I\| \le \eta; moreover, for every sufficiently large nn there is a real orthogonal n×nn \times n matrix OO such that J=(0OO∗0)J = \begin{pmatrix} 0 & O \\ O^* & 0 \end{pmatrix} and Z=(I00−I)Z = \begin{pmatrix} I & 0 \\ 0 & -I \end{pmatrix} on a set YY of size 2n2n satisfy ∥PSJPT∥≤η\|P_S J P_T\| \le \eta whenever ∣S∣,∣T∣≤4β∣Y∣|S|, |T| \le 4\beta|Y|.

Let A,BA, B be positive operators on a Hilbert space EE with 12I≤A,B≤2I\frac{1}{2}I \le A, B \le 2I, A−B=hΓA - B = h\Gamma, Γ∗=Γ\Gamma^* = \Gamma, ∥Γ∥≤1\|\Gamma\| \le 1, 0≤h≤180 \le h \le \frac{1}{8}, and let PP be an orthogonal projection commuting with BB, R=PER = PE, with ∥PΓP∥≤η\|P\Gamma P\| \le \eta (0≤η≤10 \le \eta \le 1). Then there is a specified invertible operator SRS_R such that SR∗ASR=BS_R^* A S_R = B, SR(R)=RS_R(R) = R, ∥SR−I∥≤Ch\|S_R - I\| \le Ch, and ∥(SR−I)P∥≤Chη\|(S_R - I)P\| \le Ch\eta for an absolute constant CC (and similarly in the BB-norm, and for nested subspaces R⊆R′R \subseteq R').

There are numerical constants CC and h0>0h_0 > 0 such that, for the circuit construction of Section 4 with h≤h0h \le h_0 and 0<η≤1/40 < \eta \le 1/4, ∥Vqp{p,q}−Vqp{p,q,r}∥≤Ch+CNη+CNhη\|V_{qp}^{\{p,q\}} - V_{qp}^{\{p,q,r\}}\| \le Ch + CN\eta + CNh\eta for every three configurations p,q,rp, q, r, independent of alphabet cardinalities and configurations.

For all but a proportion 2Nβ2N\beta of labels i∈Ii \in \mathcal{I}, ∥μ(si)ui−ri∥≤CNη+CNhη\|\mu(s_i)u_i - r_i\| \le CN\eta + CNh\eta.

For any unitary representation ρ:G→U(H)\rho : G \to \mathcal{U}(H), the unit vectors ψ=∣I∣−1/2∑i∈Iei⊗ρ(si)ui\psi = |\mathcal{I}|^{-1/2} \sum_{i \in \mathcal{I}} e_i \otimes \rho(s_i)u_i and r=∣I∣−1/2∑i∈Iei⊗rir = |\mathcal{I}|^{-1/2} \sum_{i \in \mathcal{I}} e_i \otimes r_i in CI⊗H\mathbb{C}^{\mathcal{I}} \otimes H satisfy ⟨ψ,(D⊗I)ψ⟩=0\langle \psi, (D \otimes I)\psi \rangle = 0 and ⟨r,(D⊗I)r⟩=12\langle r, (D \otimes I)r \rangle = \frac{1}{2}; in particular, ∥r−ψ∥≥14\|r - \psi\| \ge \frac{1}{4}.

Methods

Constructing compatible sparse flags on a nonamenable discrete group GG from a non-singleton compact Hausdorff boundary KK via strong proximality, Hahn-Banach separation, Riesz representation, and a backward stage-by-stage choice of open neighborhoods.

Source excerpts

“Lemma 2.1 (Uniform lists with a prescribed point). Let K be a compact Hausdorff boundary, let U ⊆ K be nonempty and open, let ζ ∈ K, and let 0 < β < 1. There is a finite nonempty list s1, . . . , sM ∈ G, with repetitions allowed, such that s−1_j ζ ∈ U (1 ≤ j ≤ M), 1/M #{j : s−1_j t /∈ U} < β (t ∈ K).” · Show in paper

“Fix points ξ, ζ ∈ K and choose an integer C > 1/β. We construct nonempty open sets U0, . . . , UN and the stage maps backwards, starting with UN = K.” · Show in paper

Using concentration of measure on Haar-distributed orthogonal matrices, 1/41/4-nets, and a union bound to construct pairs of orthonormal bases and anticommuting symmetric involutions with small sparse restrictions.

Source excerpts

“Let O be Haar distributed on the orthogonal group of Rm. For fixed real unit vectors u, v, the random variable u*Ov has the distribution of the first coordinate of a uniform point on the unit sphere.” · Show in paper

Constructing level-dependent inner products Gk=I+h∑k<d≤LγdG_k = I + h \sum_{k < d \le L} \gamma_d and a quadratic-form obstruction D=L−1/2∑d=1LγdD = L^{-1/2} \sum_{d=1}^L \gamma_d via the Jordan-Wigner parity-string construction.

Source excerpts

“On the formal orthonormal label space CI define γd = fd(Xd)Z1 · · · Zd−1 Jd, D = 1/√L ∑_{d=1}^L γd. (4.3) This uses the Jordan–Wigner parity-string construction [7]; see also [2, Section 6].” · Show in paper

Building unitary circuits WpCW_p^{\mathcal{C}} and pairwise comparisons VqpC=WqC(WpC)−1V_{qp}^{\mathcal{C}} = W_q^{\mathcal{C}} (W_p^{\mathcal{C}})^{-1} using Schur-complement metric transfers SeCS_e^{\mathcal{C}} that preserve the next layer's departure subspace.

Source excerpts

“The stage-k layer M^Cp,kC_{p,k} applies (4.17) on every switchable edge flagged F in p, and is identity on the orthogonal complement of their endpoint subspaces. ... Define W^C_p = M^Cp,NC_{p,N} · · · M^Cp,1C_{p,1}, V^CqpC_{qp} = W^C_q (W^C_p)^{−1}. (4.18)” · Show in paper