Dictator-to-XOR Lipschitz inverse gap

AX_lipschitz_bijection_dictator_xor_inverse

Source: arXiv:1812.09215 — Lipschitz bijections between boolean functions

Informal Question (Section 2) · arXiv:1812.09215

arXiv Question medium confidence— first stated 2021-12-10

Authors: Tom Johnston, Alex Scott

Status ai-disproved high confidence

No: every such bijection satisfies n <= 1+(k-1)+...+(k-1)^(D-1), where D is its inverse Lipschitz constant, and linear 2-Lipschitz tree maps attain the resulting bound.

Auto-reviewed 2026-09-17 with gpt-6-astra.

AI-generated write-up ai-disproved

Open the PDF write-up

This is a model-generated research artifact, not a peer-reviewed publication or a formally verified proof.

Question. Does there exist a map $\phi$ from Dictator to XOR which is $C$-Lipschitz, where each output bit depends on at most $k$ input bits, and such that $\phi^{-1}$ is $o(\log n / \log k)$-Lipschitz as $n, k \to \infty$?

Context

Theorem 1 shows that for general maps the inverse must be at least $\Omega(1/k)\cdot\log n$-Lipschitz, while for linear maps the bound is $\Omega(1/\log k)\cdot\log n$-Lipschitz. Rao and Shinkar's construction achieves $\delta(2,k)=O(1/\log k)$ for linear maps, matching the linear-map lower bound, but a gap remains for general maps between $\Omega(1/k)$ and $O(1/\log k)$.

Notes. Stated in running prose as 'This raises the following question:' without a labelled theorem environment.

Source paper

Lipschitz bijections between boolean functions
Tom Johnston, Alex Scott · 2021-12-10
https://arxiv.org/abs/1812.09215 PDF source