lemmaroutine

Low-influence functions rarely collide under coupling

Low-influence functions of equal small mean rarely collide under any coupling

controls pairs of ordering coordinates in soundness

Lemma·lem:ordering-collision·§A.2 The finite ordering transfer

Statement (paper)

For every

0<\kappa<1/2

, there is

\mu_0(\kappa)>0

. For each

m\ge2

, there is a nonnegative function

r_c^{m,\kappa}(t)\to0

t\downarrow0

with the following property, uniformly over all

R\ge1

. Let

F,G:[m]^R\to[0,1]

have the same mean

0<\mu\le\mu_0(\kappa)

and satisfy

\operatorname{Inf}_\ell(T_{1-\kappa}F)\le t,\qquad \operatorname{Inf}_\ell(T_{1-\kappa}G)\le t \quad(\ell\in[R]).

For every coupling

(Z,Z')

whose two marginals are uniform on

[m]^R

\mathbb E\bigl[ (T_{1-2\kappa}F)(Z)(T_{1-2\kappa}G)(Z')\bigr] \le \mu^{1+\kappa/2}+r_c^{m,\kappa}(t).

The function

r_c^{m,\kappa}

is independent of

R,\mu,F,G

and the coupling.

In plain English

Let

F,G:[m]^R\to[0,1]

have the same small mean

\mu\le\mu_0(\kappa)

and all influences of

T_{1-\kappa}F

and

T_{1-\kappa}G

at most

t

. Then for any coupling

(Z,Z')

of two uniform points of

[m]^R

\mathbb E[(T_{1-2\kappa}F)(Z)(T_{1-2\kappa}G)(Z')]\le \mu^{1+\kappa/2}+r_c^{m,\kappa}(t)

, where

r_c^{m,\kappa}(t)\to0

t\downarrow0

independently of

R,\mu,F,G

and the coupling.

Why it's here

This is a collision bound: for low-influence functions of equal small mean, even an arbitrary coupling of the two inputs cannot make both smoothed functions large together much beyond

\mu^{1+\kappa/2}

, which is well below

\mu

. The finite ordering transfer uses it, through the error term

r_c(t)

, to bound the payoff contribution of pseudorandom vertices on pairs of ordering coordinates, giving the local payoff bound and the final gap.

Classified routine:

Likely follows from the invariance principle / Majority-is-Stablest bounds (Mossel–O'Donnell–Oleszkiewicz 2010), which make the smoothed low-influence functions have small higher moments. Cauchy–Schwarz or Hölder then applies under any coupling with uniform marginals.

Uses

Nothing else in the paper

Used by

propFinite ordering transfer from Unique GamesclaimPseudorandom vertices have local payoff boundclaimParameter choices give final ordering gap

Sources

PaperOpen

Section: §A.2 The finite ordering transfer
Page: —
Label: lem:ordering-collision
Line: appendices/finite-consequences.tex:433

Leannot aligned

Phase 2 aligns this node to a Lean declaration.