Abstract 1 Introduction 2 Notation 3 Similarities, LSH, and Distortion 4 Upper Bound for Ulam Similarity 5 Lower Bound for Ulam Similarity 6 Upper Bound for Cayley Similarity 7 Lower Bound for Cayley Similarity 8 Conclusions and Open Questions References

On the LSH Distortion of Ulam and Cayley Similarities

Flavio Chierichetti ORCID Reddit, San Francisco, CA, USA    Mirko Giacchini ORCID Department of Computer Science, Sapienza University of Rome, Italy    Ravi Kumar ORCID Google Research, Mountain View, CA, USA    Erasmo Tani ORCID Department of Computer Science, Sapienza University of Rome, Italy
Abstract

Locality-sensitive hashing (LSH) has found widespread use as a fundamental primitive, particularly to accelerate nearest neighbor search. An LSH scheme for a similarity function S:𝒳×𝒳→[0,1] is a distribution over hash functions on 𝒳 with the property that the probability of collision of any two elements x,y∈𝒳 is exactly equal to S⁢(x,y). However, not all similarity functions admit exact LSH schemes. The notion of LSH distortion measures how multiplicatively close a similarity function is to having an LSH scheme.

In this work, we study the LSH distortion of the Ulam and Cayley similarities, which are popular similarity measures on permutations of n elements. We show that the Ulam similarity admits a sublinear LSH distortion of O⁢(n/log⁡n); we also prove a lower bound of Ω⁢(n0.12) on the best LSH distortion achievable. On the other hand, we show that the LSH distortion of the Cayley similarity is Θ⁢(n).

Keywords and phrases:
Locality-sensitive Hashing, Ulam metric, Cayley Metric, Distortion, Permutations, Representation Theory
Category:
RANDOM
Funding:
Flavio Chierichetti: Work done in part while at Sapienza University of Rome. Supported in part by BiCi – Bertinoro international Center for informatics, by a Google Focused Research Award and by the PRIN project 20229BCXNW (funded by the European Union – Next Generation EU, Mission 4 Component 1 CUP B53D23012910006).
Copyright and License:
[Uncaptioned image] © Flavio Chierichetti, Mirko Giacchini, Ravi Kumar, and Erasmo Tani; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation → Data structures design and analysis
; Information systems → Similarity measures ; Theory of computation → Lower bounds and information complexity ; Theory of computation → Nearest neighbor algorithms
Related Version:
Full Version: https://arxiv.org/abs/2605.11921
Acknowledgements:
The authors wish to thank Alessandro Panconesi for providing useful ideas for the project.
Editors:
Mohit Singh and Tom Gur

1 Introduction

Locality-sensitive hashing (LSH) is an important tool for processing high dimensional data [4, 5, 13, 12]. Classic examples of LSH include minHash for the Jaccard similarity [4, 5], simHash for the cosine similarity [6], and sampling hash for the Hamming similarity [12]. LSH has been extensively used for solving (approximate) nearest-neighbor search [1] and similarity search [11, 16, 20]; see https://www.mit.edu/˜andoni/LSH/ for more pointers on classical results.

LSH is a way to represent a similarity S – which in the context of this paper is a bi-variate, reflexive, symmetric function – by a distribution over partitions. These partitions correspond to the pre-images of hash functions, so that two entities are considered similar by a hash function if they both hash to the same value. In other words, an LSH family ℋ induces a collision kernel of the form S⁢(x,y)=Prh∼ℋ⁡[h⁢(x)=h⁢(y)], for entities x,y in the universe.

Such collision kernels have to satisfy two constraints: they have unit diagonals (capturing reflexivity) and are a convex combination of equivalence-relation matrices (capturing hashing to the same value). Hence, it turns out that many natural and useful similarity measures do not admit an LSH. An interesting line of work studies which similarities have an LSH. Charikar [6] identified a necessary condition for a similarity to admit an LSH: the corresponding distance function (which is often one minus the similarity) must be a metric and must be isometrically embeddable into ℓ1.

To circumvent this, Chierichetti et al. [9] introduced the notion of LSH distortion, which answers the question: how much is a non-LSHable similarity S multiplicatively close to an LSHable similarity?

Formally, given a similarity S that does not admit an LSH, is there another similarity S′ that has an LSH and satisfies:

∀x,y:1Δ⋅S(x,y)≤S′(x,y)≤S(x,y)? (1)

We call the optimal Δ in (1) the LSH distortion of S.

In their paper, Chierichetti et al. showed tight LSH distortion bounds for several set similarities. Note that, since we are considering multiplicative approximations over similarities, and we wish to achieve them using collision kernels, the LSH distortion of a similarity can differ significantly from its metric counterpart, and known results for metric distortion do not transfer to this setting.

Our contributions

In this work, we study the LSH distortion of two natural similarities derived from popular metrics on permutations. The first is the normalized Ulam similarity, which measures the length of the longest common subsequence between two permutations. The second is the Cayley similarity, which is the normalized number of cycles in the relative permutation (its distance counterpart is number of transpositions needed to turn one permutation into another).

Our main results are the following:

  • ■

    We show that the Ulam similarity has sublinear LSH distortion. In particular, we show that it can be approximated by a similarity that has an LSH, with distortion O⁢(n/log⁡n) (Theorem 5),

  • ■

    We also show a lower bound of Ω⁢(n0.12) on the LSH distortion of the Ulam similarity (Theorem 10),

  • ■

    In contrast, we show that the Cayley similarity has an Ω⁢(n) lower bound on its LSH distortion (Theorem 19), matching a simple O⁢(n) upper bound (Theorem 18).

Techniques

The proof of the upper bound for the Ulam similarity is based on computing a suitable measure of correlation between the given permutation and a random permutation. The collision probability of our scheme depends on how well the input permutations are correlated with a random one. Showing that the collision probability is upper bounded by LCS⁢(⋅,⋅)/n is relatively easy. On the other hand, showing it is also lower bounded by the LCS (up to sublinear distortion) is more challenging.

For the lower bounds on the distortion, we crucially utilize the PSDness of the collision kernel (Lemma 4). The lower bound for the Ulam similarity is based on first constructing a small set of permutations on an 8-element universe that has an LSH distortion of at least 9/7, and then amplifying its cardinality to work for a universe of arbitrarily large size, by using the wreath product on permutations.

The lower bound for the Cayley similarity is based on representation theory, and uses both the fact that every bi-invariant PSD kernel on 𝕊n can be written as a convex combination of normalized characters, as well as Roichman’s character-ratio estimates applied to derangements. The distortion lower bound is obtained by constructing two derangements that share the high-order terms of this decomposition and hence must have close collision probabilities with the identity permutation, but have vastly different Cayley similarities (linear vs constant) to it.

Related work

For permutation metrics, the Ulam metric has been extensively studied through its connection to edit distance and longest common subsequences. Charikar and Krauthgamer [8] proved that the Ulam metric embeds into ℓ1 with O⁢(log⁡n) distortion; Andoni and Krauthgamer [3] later proved that embeddings of the Ulam metric into ℓ1 requires a near-tight distortion of Ω⁢(log⁡n/log⁡log⁡n). Andoni et al. [2] bypassed the ℓ1 barrier by embedding Ulam distance with constant distortion into an iterated product metric. Charikar et al. [7] obtained an O⁢(log⁡n) distortion randomized embedding of Ulam into Hamming space that also carries alignment information. Note that all these previous results are for the Ulam metric; to the best of our knowledge, the corresponding question of Ulam similarity has not been considered in the literature.

Unlike Ulam, the Cayley metric is not hard to embed into ℓ1. Our work can be viewed as a hardness result for LSHability of the Cayley similarity.

Outline

We begin, in Section 2, by introducing some basic notation. In Section 3, we review the definition of LSH distortion and introduce in detail the central problems of the paper. In Section 4, we provide our O⁢(n/log⁡n) upper bound on the LSH distortion for the Ulam similarity. We then give a Ω⁢(n0.12) lower bound in Section 5. In Section 6, we give a simple O⁢(n) upper bound on the distortion of the Cayley similarity, that we complement with a matching lower bound in Section 7.

In the appendix of the full version of the paper, we also review some background on the representation theory of 𝕊n, which we rely on for our proofs in Section 7.

2 Notation

Permutations

For a positive integer n, let [n]:={1,…,n}. Let 𝕊n be the set of all permutations of [n]. We denote by id the identity permutation. For a permutation π∈𝕊n we will sometimes use the one-line notation and sometimes the cycle decomposition.111For example, for the permutation π:[5]→[5] such that π⁢(1)=3, π⁢(2)=5, π⁢(3)=1, π⁢(4)=2, π⁢(5)=4; the one-line representation is (3,5,1,2,4) and the cycle decomposition is (1  3)⁢(2  5  4). For a permutation π∈𝕊n we denote with c⁢(π) the number of cycles in its cycle decomposition. Note that c⁢(π)=c⁢(π−1)=c⁢(σ⁢π⁢σ−1) for any σ∈𝕊n. For π∈𝕊n, a,b∈[n] we write a<πb to indicate that a comes before b in the one-line representation of π (alternatively that π−1(a)<π−1(b)). We write a≤πb to indicate that either a=b or a<πb. For π,σ∈𝕊n we denote with LCS⁢(π,σ) the length of the longest common subsequence between the one-line representations of π and σ. For π∈𝕊n, we denote with fix⁢(π) the number of fixed points of π and with cycle2⁢(π) the number of cycles of length two in the cycle decomposition of π. We also let supp(π)=n−fix⁢(π).

Partitions and Compositions

Recall that, for any positive integer n, a partition λ=(λ1,…,λr) of n is a finite sequence of non-increasing positive integers that sum to n. We write λ⊢n to indicate that λ is a partition of n. We denote by (1n) the partition (1,…,1) containing n 1s. Given a partition λ=(λ1,…,λr)⊢n its transpose partition (sometimes also called the conjugate partition) is the partition λ′⊢n defined by λ′=(λ1′,…,λλ1′), where:

∀i∈[λ1]:λi′=max⁡{k∣λk≥i}.

A composition of n is an ordered partition of n, i.e., an integer vector μ=(μ1,…,μℓ) such that μi≥0 for every i∈[ℓ] and ∑i∈[ℓ]μi=n.

Matrices

A symmetric matrix M∈ℝn×n is positive semidefinite (PSD, written M⪰0) if for all x∈ℝn, we have:

xT⁢M⁢x≥0.

The trace operator is the function that takes in a square matrix M∈ℝn×n and returns tr⁢(M)=∑i∈[n]M⁢(i,i). Given two square matrices X,Y, we denote by diag⁡(X,Y) the block matrix:

diag⁡(X,Y)=(X𝟎𝟎Y,)

where 𝟎 is the all-zeros matrix.

3 Similarities, LSH, and Distortion

Definition 1 (Similarity).

Given a set 𝒳, a similarity (or similarity function) on 𝒳 is a function S:𝒳×𝒳→[0,1], satisfying:

(a) Reflexivity:

S⁢(x,x)=1 for all x∈𝒳,

(b) Symmetry:

S⁢(x,y)=S⁢(y,x) for all x,y∈𝒳.

A similarity space is simply a pair (𝒳,S), where 𝒳 is a set, and S is a similarity function on 𝒳.

Given a similarity space, it is natural to ask whether one can find a small representation for elements of 𝒳 that preserve the values of S⁢(⋅,⋅). A natural approach to obtaining this is locality-sensitive hashing, which aims to construct randomized embeddings of 𝒳 into discrete (0-1) similarity spaces that preserve S⁢(⋅,⋅) in expectation. We recall the key definition here.

Definition 2 (Locality-Sensitive Hashing (LSH)).

A locality-sensitive hashing (LSH) scheme for a similarity space (𝒳,S) is a distribution ℋ over functions from 𝒳 into some finite set 𝒴 with the property that:

Prh∼ℋ⁡[h⁢(x)=h⁢(y)]=S⁢(x,y),

for all x,y∈𝒳.

We say that a similarity function S is LSHable if it admits an LSH scheme.

Chierichetti et al. [9] give a notion of distortion for similarity functions, quantifying the degree to which non-LSHable similarities are far from being LSHable. We recall the key definitions.

Definition 3 ([9]).

We say a distribution ℋ over functions from 𝒳 to some finite set 𝒴 Δ-approximates the space (𝒳,S), if:

1Δ⋅S⁢(x,y)≤Prh∼ℋ⁡[h⁢(x)=h⁢(y)]≤S⁢(x,y),

for all x,y∈𝒳. The LSH distortion (or simply distortion) of a similarity space (𝒳,𝒮) is the smallest Δ≥1 such that there exists a distribution ℋ that Δ-approximates (𝒳,S).

A simple argument shows that the distortion of a similarity space (𝒳,S) could be characterized as the smallest Δ≥1 such that there exists an LSHable similarity function S′:𝒳×𝒳→[0,1] with the property that:

1Δ⋅S⁢(x,y)≤S′⁢(x,y)≤S⁢(x,y), (2)

for all x,y∈𝒳.

The focus of this work is the distortion of two similarity spaces in which 𝒳 is the symmetric group 𝕊n: the Ulam similarity and the Cayley similarity.

Ulam Similarity

The Ulam distance between two permutations π,σ∈𝕊n is defined as

dU⁢(π,σ):=n−LCS⁢(π,σ),

We define the (normalized) Ulam similarity in a natural way:

SU⁢(π,σ)=1−n−LCS⁢(π,σ)n=LCS⁢(π,σ)n.

Cayley Similarity

The Cayley distance between two permutations π,σ∈𝕊n is defined as the minimum number of (not necessarily adjacent) transpositions required to transform one permutation into the other, and it is also equivalent to dC⁢(π,σ):=n−c⁢(π−1⁢σ)=n−c⁢(π⁢σ−1) (see, e.g., [10, page 118]). We define a notion of (normalized) Cayley similarity in a natural way:

SC⁢(π,σ)=1−dC⁢(π,σ)n=c⁢(π−1⁢σ)n.

Positive Semi-Definiteness

In order to prove lower bounds on the achievable distortion, we will use the following result. Let ℋ be a probability distribution over functions from a finite domain 𝒳 into a finite range 𝒴. Fixing any ordering of the elements of 𝒳, we define the matrix Pℋ∈ℝ|𝒳|×|𝒳| such that:

Pℋ⁢(x1,x2):=Prh∼ℋ⁡[h⁢(x1)=h⁢(x2)],

for x1,x2∈𝒳.

We now show that this matrix is always PSD.

Lemma 4.

For any distribution ℋ over functions from 𝒳 to 𝒴, where 𝒳 and 𝒴 are finite sets, the matrix Pℋ is PSD. That is, for all {wx}x∈𝒳∈ℝ|𝒳|, we have:

∑x1∈𝒳∑x2∈𝒳wx1⁢wx2⁢Pℋ⁢(x1,x2)≥0.

Proof.

Note that for any x1,x2∈𝒳,

P⁢(x1,x2)=Prh∼ℋ⁡[h⁢(x1)=h⁢(x2)]=𝔼h∼ℋ⁢[𝟏[h⁢(x1)=h⁢(x2)]],

where 𝟏[⋅] is the indicator function, and hence:

∑x1∈𝒳∑x2∈𝒳wx⁢wy⁢P⁢(x1,x2) =∑x1∈𝒳∑x2∈𝒳wx⁢wy⁢𝔼h∼ℋ⁢[𝟏[h⁢(x1)=h⁢(x2)]]
=𝔼h∼ℋ⁢[∑x1∈𝒳∑x2∈𝒳wx1⁢wx2⁢𝟏[h⁢(x1)=h⁢(x2)]].

Now, for a fixed h:𝒳→𝒴, we show that the inner sum is non-negative, which in turns completes the proof. We have:

∑x1∈𝒳∑x2∈𝒳wx1⁢wx2⁢𝟏[h⁢(x1)=h⁢(x2)]=∑y∈𝒴∑x1∈𝒳:h⁢(x1)=y∑x2∈𝒳:h⁢(x2)=ywx1⁢wx2=∑y∈𝒴(∑x∈𝒳:h⁢(x)=ywx)2≥0.

◀

4 Upper Bound for Ulam Similarity

In this section, we prove the following result:

Theorem 5.

The LSH distortion of (𝕊n,SU) is O⁢(n/log⁡n).

For two permutations τ,π∈𝕊n and z∈[n], define:

Recτ,z⁡(π):={a∈[n]∣z≤πa⁢ and ⁢b<τa⁢ for all b such that ⁢z≤πb<πa}.

Intuitively, Recτ,z⁡(π) is the set of new record maxima according to τ obtained while scanning the one-line representation of π starting from z.

For τ,π∈𝕊n, a,z∈[n] define:

hτ,z,a⁢(π):={1 if ⁢a∈Recτ,z⁡(π),π otherwise.

Let ℋ be the uniform distribution over the set of functions: {hτ,z,a∣τ∈𝕊n,z∈[n],a∈[n]}. Recall that for π,σ∈𝕊n:

Pℋ⁢(π,σ):=Prhτ,z,a∼ℋ⁡[hτ,z,a⁢(π)=hτ,z,a⁢(σ)].

We will show that: O⁢(log⁡n/n)⋅SU⁢(π,σ)≤Pℋ⁢(π,σ)≤SU⁢(π,σ).

Lemma 6.

For π,σ∈𝕊n, π≠σ, it holds that:

Pℋ⁢(π,σ)=1n⋅𝔼τ,z⁢[|Recτ,z⁡(π)∩Recτ,z⁡(σ)|].

Proof.

Note that for π≠σ, we have that hτ,z,a⁢(π)=hτ,z,a⁢(σ) if and only if a∈Recτ,z⁡(π)∩Recτ,z⁡(σ). Conditioned on the choice of τ and z, there are n possible values for a and only |Recτ,z⁡(π)∩Recτ,z⁡(σ)| of them make the hashes of π and σ equal. This concludes the proof. ◀

Lemma 7.

For any τ,π,σ∈𝕊n and z∈[n], it holds that:

1≤|Recτ,z⁡(π)∩Recτ,z⁡(σ)|≤LCS⁢(π,σ).

Proof.

Since z∈Recτ,z⁡(π)∩Recτ,z⁡(σ), the set Recτ,z⁡(π)∩Recτ,z⁡(σ) is always non-empty, proving the first inequality.

We now show the second inequality. If there is only one element in the intersection, the result is trivially true, since LCS⁢(π,σ)≥1 for any π,σ∈𝕊n. Otherwise, consider any distinct x,y∈Recτ,z⁡(π)∩Recτ,z⁡(σ). Suppose without loss of generality that x<πy. By definition of Recτ,z⁡(π), since y is observed after x in the one-line representation of π, it must hold that x<τy. Moreover, we have x<σy, for otherwise we would have x>τy, leading to a contradiction.

Therefore, if we let Recτ,z⁡(π)∩Recτ,z⁡(σ)=r1<π⋯<πrt, we also have r1<σ⋯<σrt, meaning that r1,…,rt is a common subsequence of π and σ, and therefore t≤LCS⁢(π,σ). ◀

Fixed π,σ such that LCS⁢(π,σ)≥2, define L:=LCS⁢(π,σ) and let C=(c1,…,cL) be a longest common subsequence. For 1≤i<j≤L, define the intervals:

Ii,jπ:={x∈[n]∣ci≤πx≤πcj},andIi,jσ:={x∈[n]∣ci≤σx≤σcj}.

Define also Wi,j:=|Ii,jπ∪Ii,jσ|.

Lemma 8.

For any π,σ∈𝕊n such that L:=LCS⁢(π,σ)≥2, it holds that:

Pℋ⁢(π,σ)≥1n2⋅∑1≤i<j≤L1Wi,j.

Proof.

Consider the case π≠σ, otherwise the result is trivial, since the right-hand side is always less than 1. For τ∈𝕊n, and 1≤i<j≤L, suppose that:

cj≥τx  for all ⁢x∈Ii,jπ∪Ii,jσ.

Under this assumption, it holds that: cj∈Recτ,ci⁡(π)∩Recτ,ci⁡(σ). Indeed, we have that cj is the maximum (according to τ) of all indices Ii,jπ between ci and cj in the one-line representation of π and therefore it will be added to Recτ,z⁡(π) when starting from z=ci (and the same argument holds for σ).

By Lemma 6 and the remark above, we have:

Pℋ⁢(π,σ) =1n⋅𝔼τ,z⁢[|Recτ,z⁡(π)∩Recτ,z⁡(σ)|]
≥1n⋅∑i=1L−1Pr⁡[z=ci]⋅𝔼𝜏⁢[|Recτ,z⁡(π)∩Recτ,z⁡(σ)||z=ci]
=1n⋅∑i=1L−11n⋅∑j=1nPrτ⁡[j∈Recτ,ci⁡(π)∩Recτ,ci⁡(σ)]
≥1n2⁢∑i=1L−1∑j=i+1LPrτ⁡[cj∈Recτ,ci⁡(π)∩Recτ,ci⁡(σ)]
≥1n2⁢∑i=1L−1∑j=i+1LPrτ⁡[cj≥τx⁢ for all ⁢x∈Ii,jπ∪Ii,jσ]
=1n2⁢∑i=1L−1∑j=i+1L1Wi,j,

where the last inequality follows from the remark above and the last equality uses that for a uniform at random τ∈𝕊n, the element ranked highest among Ii,jπ∪Ii,jσ is chosen uniformly at random among its elements. ◀

Lemma 9.

For any π,σ∈𝕊n such that L:=LCS⁢(π,σ)≥4, it holds that:

∑1≤i<j≤L1Wi,j≥L2⁢ln⁡L32⁢n.

Proof.

For 1<t≤L, define:

wt:=|It−1,tπ|+|It−1,tσ|.

For 1≤i<L and 1≤d≤L−i, define Si,d:=∑t=i+1i+dwt. Note that, for 1≤i<j≤L, we have:

Wi,j≤|Ii,jπ|+|Ii,jσ|≤∑t=i+1jwt=Si,(j−i). (3)

Therefore, we have:

∑1≤i<j≤L1Wi,j=∑i=1L−1∑j=i+1L1Wi,j⁢≥(3)⁢∑i=1L−1∑j=i+1L1Si,(j−i)=∑i=1L−1∑d=1L−i1Si,d=∑d=1L−1∑i=1L−d1Si,d. (4)

For a fixed 1≤d<L, by the Cauchy–Schwarz inequality, we have:

(∑i=1L−d1Si,d)⋅(∑i=1L−dSi,d)≥(∑i=1L−d1Si,d⋅Si,d)2=(L−d)2. (5)

Note that each element of [n] can be counted at most twice in wt and it can appear in at most two wt’s, therefore:

∑t=2Lwt≤4⁢n.

Moreover, each wt can appear in at most d distinct Si,d for i∈{1,…,L−d}, giving:

∑i=1L−dSi,d≤d⁢∑t=2Lwt≤4⋅d⋅n.

Combining this inequality with (5) gives:

∑i=1L−d1Si,d≥(L−d)2∑i=1L−dSi,d≥(L−d)24⋅d⋅n.

Plugging this inequality into (4) we obtain:

∑1≤i<j≤L1Wi,j≥∑d=1L−1(L−d)24⋅d⋅n≥∑d=1⌊L/2⌋(L−d)24⋅d⋅n≥L216⁢n⁢∑d=1⌊L/2⌋1d≥L2⁢ln⁡L32⁢n,

where the last inequality uses that for L≥4:

∑d=1⌊L/2⌋1d≥ln⁡(⌊L/2⌋+1)≥ln⁡(L)=ln⁡L2.

◀

We are now ready to prove the main result of this section:

Proof of Theorem 5.

It is sufficient to show that for each π,σ∈𝕊n it holds that:

Θ⁢(log⁡n/n)⋅SU⁢(π,σ)≤Pℋ⁢(π,σ)≤SU⁢(π,σ).

Note that if π=σ then Pℋ⁢(π,σ)=SU⁢(π,σ)=1. Therefore, consider the case where π≠σ. By combining Lemma 6 and Lemma 7 we have:

1n≤Pℋ⁢(π,σ)≤LCS⁢(π,σ)n=SU⁢(π,σ). (6)

Therefore, we only have to prove Pℋ⁢(π,σ)≥Ω⁢(log⁡n/n)⋅SU⁢(π,σ) to conclude the proof. Consider first the case where LCS⁢(π,σ)≤3. In this case we have:

Pℋ⁢(π,σ)≥1n≥13⋅LCS⁢(π,σ)n=13⋅SU⁢(π,σ).

Consider now the case LCS⁢(π,σ)≥4 and denote L:=LCS⁢(π,σ). By combining Lemma 8 and Lemma 9 we obtain:

Pℋ⁢(π,σ)≥L2⁢ln⁡L32⋅n3=L⁢ln⁡L32⋅n2⋅SU⁢(π,σ). (7)

By (6) we also have:

Pℋ⁢(π,σ)≥1L⋅SU⁢(π,σ). (8)

We split the case LCS⁢(π,σ)≥4 in two sub-cases. Suppose first that LCS⁢(π,σ)≤nln⁡n. Then, (8) gives: Pℋ⁢(π,σ)≥ln⁡n/n⋅SU⁢(π,σ). Suppose instead that LCS⁢(π,σ)>nln⁡n. Then, by (7) we have:

Pℋ⁢(π,σ)≥nln⁡n⁢ln⁡(nln⁡n)32⁢n2⋅SU⁢(π,σ)=(ln⁡n−12⁢ln⁡ln⁡n32⋅ln⁡n⋅n)⋅SU⁢(π,σ)≥ln⁡n64⋅n⋅SU⁢(π,σ),

where we used that ln⁡n2≥ln⁡ln⁡n2 for n≥3. ◀

5 Lower Bound for Ulam Similarity

In this section, we prove the following result.

Theorem 10.

Let n be any integer of the form 82k, for integer k≥0. The LSH distortion of (𝕊n,SU) is Ω⁢(nδ), where δ≥0.12.

At a high level, we obtain a lower bound on the LSH distortion by starting with a small instance that exhibits constant distortion, and then iteratively amplifying it to handle larger values of n. In each step, both the distortion bound and the permutation domain grow quadratically. Our base case has n=8, therefore our construction produces instances for any n of the form 82k, where k is a non-negative integer. The main tool enabling this amplification is the wreath product.

For any two subsets A,B⊆𝕊n, we define the similarity matrix MA,B∈ℝ|A|×|B| by MA,B⁢(π,σ)=SU⁢(π,σ) for any π∈A and σ∈B. For simplicity, when A and B are the same, we will adopt a lighter notation, and denote by MA the matrix MA,A. We note that the matrix M(A∪B) has a simple block structure:

M(A∪B)=(MAMA,BMB,AMB),

where we fixed an ordering in which the permutations in A come before those in B.

Definition 11 (Witness).

For n>0, let A,B⊆𝕊n be disjoint subsets such that |A|=|B| and MA=MB. Let W∈ℝ(|A|+|B|)×(|A|+|B|) be a PSD block matrix such that:

W=(U−V−VTU)⪰0,

where U,V∈ℝ|A|×|A| are entry-wise non-negative symmetric matrices such that tr⁢(U⋅MA)≠0.We call the triple (A,B,W) a witness of size n and we define its value to be:

ν⁢(A,B,W):=tr⁢(V⋅MA,B)tr⁢(U⋅MA).

We now show that the existence of a witness implies a lower bound to the LSH distortion for Ulam similarity on 𝕊n.

Lemma 12.

Let (A,B,W) be a witness of size n (Definition 11). Then, the LSH distortion for Ulam similarity space (𝕊n,SU) is at least the value of the witness, ν⁢(A,B,W), even when restricted only to permutations in A∪B⊆𝕊n.

Proof.

Consider any distribution ℋ over functions on 𝕊n which Δ-approximates (A∪B,SU) for Δ≥1. For every π,σ∈A∪B we have:

MA∪B⁢(π,σ)Δ=SU⁢(π,σ)Δ≤Pℋ⁢(π,σ)≤SU⁢(π,σ)=MA∪B⁢(π,σ). (9)

Note that, having fixed an ordering of the elements of A∪B that puts the elements of A before the elements of B, Pℋ gets naturally divided into four square blocks:

Pℋ=(PAPA,BPB,APB).

By Lemma 4, Pℋ⪰0 and W⪰0, we have tr⁢(W⁢Pℋ)≥0. Expanding blockwise, and using VT=V and PB,AT=PA,B, we have:

tr⁢(U⁢PA)+tr⁢(U⁢PB)−2⁢t⁢r⁢(V⁢PA,B)≥0.

Note that, by Equation 9, Pℋ⁢(π,σ)≤MA∪B⁢(π,σ) and Pℋ⁢(π,σ)≥(1/Δ)⋅MA∪B⁢(π,σ) for all π,σ. Therefore, we have:

tr⁢(U⋅MA)+tr⁢(U⋅MB)≥2Δ⋅tr⁢(V⋅MA,B).

Since MA=MB, we have tr⁢(U⋅MA)=tr⁢(U⋅MB). Hence,

Δ≥tr⁢(V⋅MA,B)tr⁢(U⋅MA)=ν⁢(A,B,W).

◀

For permutations π,σ∈𝕊n the wreath product π≀σ∈𝕊n2 is defined as follows. The elements of [n2] are partitioned into n blocks where the ith block, i∈[n], contains elements Σi:={(i−1)⋅n+1,…,i⋅n}. The resulting permutation π≀σ is obtained by permuting the elements in each block with the inner permutation σ and then permuting the blocks with the outer permutation π. For two sets A,B⊆𝕊n, we define A≀B:={π≀σ∣π∈A,σ∈B}. We use the following key property of the wreath product for amplification:

Lemma 13.

For any π,σ,τ1,τ2∈𝕊n we have:

LCS⁢(π≀σ,τ1≀τ2)=LCS⁢(π,τ1)⋅LCS⁢(σ,τ2).

Proof.

In the permutation π≀σ, the blocks appear in the order given by π, and within every block the elements appear in the order given by σ; similarly for τ1≀τ2.

We first prove that LCS⁢(π≀σ,τ1≀τ2)≤LCS⁢(π,τ1)⋅LCS⁢(σ,τ2). Let Z be any common subsequence of π≀σ and τ1≀τ2. Since the alphabets Σi are pairwise disjoint, an element from a block Σi can only be matched with the same element from the same block Σi. Therefore, if we track the sequence of block indices that contribute at least one matched element to Z, then this is a common subsequence of the outer permutations π and τ1; thus, the number of contributing blocks is at most LCS⁢(π,τ1).

Let Σi be any contributing block. The matched elements of Z in this block is a common subsequence of the ordering of Σi inside π≀σ and the ordering of Σi inside τ1≀τ2. These two internal orderings are σ and τ2, relabeled with the alphabet Σi; therefore, this block contributes at most LCS⁢(σ,τ2) matched elements. Summing over all contributing blocks, we obtain LCS⁢(π≀σ,τ1≀τ2)≤LCS⁢(π,τ1)⋅LCS⁢(σ,τ2).

We now show LCS⁢(π≀σ,τ1≀τ2)≥LCS⁢(π,τ1)⋅LCS⁢(σ,τ2). Consider an optimal common subsequence of the outer permutations π and τ1, consisting of LCS⁢(π,τ1) block indices. For each such matched block Σi, consider an optimal common subsequence of the inner permutations σ and τ2, relabeled using Σi. Since the block indices appear in the same relative order in both π and τ1, concatenating these common subsequences over the chosen blocks yields a valid common subsequence of π≀σ and τ1≀τ2 of length LCS⁢(π,τ1)⋅LCS⁢(σ,τ2). ◀

We now show how to use the wreath product to amplify the size of the witness. We will make use of the Kronecker product. We recall that for two matrices X∈ℝn×m and Y∈ℝs×t, the Kronecker product X⊗Y∈ℝn⁢s×m⁢t is the following block matrix:

X⊗Y=(x11⋅Y…x1⁢m⋅Y⋮⋱⋮xn⁢1⋅Y…xn⁢m⋅Y).
Lemma 14.

Consider any disjoint sets A,B⊆𝕊n with |A|=|B|. Let A′=A≀A and B′=B≀B. Then, we have:

M(A′∪B′)=(MA⊗MAMA,B⊗MA,BMB,A⊗MB,AMB⊗MB).

Proof.

Let π,σ∈A′∪B′ and suppose that π=π1≀π2, σ=σ1≀σ2. By Lemma 13,

M(A′∪B′)⁢(π,σ) =LCS⁢(π,σ)n2=LCS⁢(π1,σ1)n⋅LCS⁢(π2,σ2)n
=M(A∪B)⁢(π1,σ1)⋅M(A∪B)⁢(π2,σ2).

Then, by considering the ordering over A′ obtained by the ordering of A when we consider first the outer permutation and then the inner permutation (and similarly for B′), we have that each entry of the matrix is equivalent to the Kronecker product. ◀

Lemma 15.

Let (A,B,W) be a witness of size n. Let A′=A≀A, B′=B≀B, and:

W′=(U⊗U−(V⊗V)−(VT⊗VT)U⊗U).

Then, (A′,B′,W′) is a witness of size n2 and ν⁢(A′,B′,W′)≥ν⁢(A,B,W)2.

Proof.

Note that U⊗U and V⊗V are non-negative and symmetric. Moreover, since W⪰0, we have that W⊗W⪰0. Define:

W′′=(U⊗UV⊗VVT⊗VTU⊗U).

Since W′′ is a principal sub-matrix of W⊗W, we have that W′′⪰0. Observe now that W′=diag⁢(I,−I)⋅W′′⋅diag⁢(I,−I), and therefore W′⪰0 since for any matrix X⪰0 and any matrix Y, Y⁢X⁢YT⪰0. Moreover, by Lemma 14 and since MA=MB, we also have MA′=MB′. Then, (A′,B′,W′) is a valid witness of size n2. We now compute its value.

For matrices A,B,C,D it holds that tr⁢((A⊗B)⁢(C⊗D))=tr⁢(A⁢C)⋅tr⁢(B⁢D). By using this property, and by Lemma 14, we have:

tr⁢((V⊗V)⋅MA′,B′) =tr⁢((V⊗V)⋅(MA,B⊗MA,B))=tr⁢(V⋅MA,B)2, and
tr⁢((U⊗U)⋅MA′) =tr⁢((U⊗U)⋅(MA⊗MA))=tr⁢(U⋅MA)2.

Note that since tr⁢(U⋅MA)≠0, tr⁢((U⊗U)⁢MA′)≠0. Then:

ν⁢(A′,B′,W′)=tr⁢((V⊗V)⋅MA′,B′)tr⁢((U⊗U)⋅MA′)=(tr⁢(V⋅MA,B)tr⁢(U⋅MA))2=ν⁢(A,B,W)2.

◀

We now provide our starting instance.

Proposition 16.

There exists a witness (A0,B0,W0) of size 8 and value ≥9/7.

Proof.

Let A0={A1,…,A4} and B0={B1,…,B4}, where τ=(1 2 7 8)⁢(3 6 5 4)=(2,7,6,3,4,5,8,1) and Bi=τ⁢Ai:

A1=(1,2,3,4,5,6,7,8),B1=(2,7,6,3,4,5,8,1),
A2=(4,3,2,1,8,7,6,5),B2=(3,6,7,2,1,8,5,4),
A3=(6,5,8,7,2,1,4,3),B3=(5,4,1,8,7,2,3,6),
A4=(7,8,5,6,3,4,1,2),B4=(8,1,4,5,6,3,2,7).

Since B0 is obtained from A0 by relabeling, we have MA0=MB0. A direct computation gives

MA0=18⁢(8222282222822228),MA0,B0=18⁢(5445455445545445).

The matrix W0 for this instance is given by U=V=J4 (where J4 is the all-ones 4×4 matrix). First,

W=(U−V−VTU)=(J4−J4−J4J4)=(1−1−11)⊗J4⪰0.

Next, it is easy to calculate

tr⁡(V⋅MA0,B0)=18⁢(18⋅4)=9,tr⁡(U⋅MA0)=18⁢(14⋅4)=7.

Hence, ν⁢(A0,B0,W0)=9/7. ◀

Lemma 17.

There exists a constant δ>0 such that, for any n0>0, there exists n≥n0 such that the LSH distortion of the Ulam similarity SU on 𝕊n is at least Ω⁢(nδ).

Proof.

Let Δ0=9/7 and m=8. Let k be the smallest integer such that m2k≥n0, we set n=m2k. Note that k=log2⁡logm⁡(n).

Starting from the witness of Proposition 16 and applying Lemma 15 k times we obtain a witness of size m2k=n and value ≥Δ02k. By Lemma 12, this implies that the LSH distortion on 𝕊n is at least:

Δ02k=Δ0logm⁡(n)=nlogm⁡Δ0≥n0.120856=Ω⁢(nδ),

for δ=0.12. ◀

Note that Lemma 17 directly implies Theorem 10. The proof is elementary.

6 Upper Bound for Cayley Similarity

In this section, we show that the LSH distortion for Cayley similarity is no more than n.

Theorem 18.

The LSH distortion of (𝕊n,SC) is at most n.

Proof.

Let ℋ be the uniform at random distribution over the functions h:𝕊n→[n]. Clearly, for each π,σ∈𝕊n, π≠σ:

Prh∼ℋ⁡[h⁢(π)=h⁢(σ)]=1n.

Since 1n≤SC⁢(π,σ)≤1 for all π,σ∈𝕊n, we have:

1n⋅SC⁢(π,σ)≤Prh∼ℋ⁡[h⁢(π)=h⁢(σ)]≤SC⁢(π,σ).

◀

7 Lower Bound for Cayley Similarity

In this section, we show the following result:

Theorem 19.

The LSH distortion of (𝕊n,SC) is Ω⁢(n).

The proof will rely on some standard results in the representation theory of 𝕊n. For convenience, we review these standard results in the appendix of the full version of the paper (see also, e.g., [19, 14, 17]).

We begin with the following definition:

Definition 20 (Bi-invariance).

We say that a function f:𝕊n×𝕊n→ℝ is bi-invariant if:

f⁢(π,σ)=f⁢(τ1⁢π⁢τ2,τ1⁢σ⁢τ2),

for any π,σ,τ1,τ2∈𝕊n. We say a bi-invariant function is a bi-invariant PSD kernel if, in addition, it satisfies:

∑π,σ∈𝕊naσ⁢aπ⁢f⁢(π,σ)≥0,

for every a∈ℝ𝕊n. We also require that f⁢(id,id)=1 for f to be a PSD kernel.

Recall that a class function on 𝕊n is a function that is constant on each conjugacy class of 𝕊n. We recall the following property of bi-invariant functions. (Note that equivalent results are known in the literature, and hold for more general groups – see, e.g., [14, Chapter 4.5] – but we include a proof anyway for completeness.)

Lemma 21.

A function f:𝕊n×𝕊n→ℝ is bi-invariant if and only if there exists a class function g:𝕊n→ℝ such that:

f⁢(σ,π)=g⁢(σ⁢π−1),

for every σ,π∈𝕊n.

Proof.

Let f:𝕊n×𝕊n→ℝ be a bi-invariant function. Define g:𝕊n→ℝ as:

g⁢(π):=f⁢(π,id).

Then we have:

f⁢(π,σ)=f⁢(π⁢σ−1,σ⁢σ−1)=f⁢(π⁢σ−1,id)=g⁢(π⁢σ−1)

for any π,σ∈𝕊n. Moreover, g is a class function, since, for any π,σ∈𝕊n:

g⁢(σ⁢π⁢σ−1)=f⁢(σ⁢π⁢σ−1,id)=f⁢(π,σ−1⁢σ)=f⁢(π,id)=g⁢(π),

where the second equality follows from the bi-invariance of f.

On the other hand, suppose that f:𝕊n×𝕊n→ℝ is a function such that f⁢(π,σ)=g⁢(π⁢σ−1) for some class function g, then, for any π,σ,τ∈𝕊n:

f⁢(π⁢τ,σ⁢τ)=g⁢(π⁢τ⁢τ−1⁢σ−1)=g⁢(π⁢σ−1)=f⁢(π,σ),

and:

f⁢(τ⁢π,τ⁢σ)=g⁢(τ⁢π⁢σ−1⁢τ−1)=g⁢(π⁢σ−1)=f⁢(π,σ),

where the second equality uses the fact that g is a class function. Hence f is bi-invariant. ◀

A crucial property of the Cayley similarity is that it is bi-invariant, as we now show.

Lemma 22.

SC⁢(⋅,⋅) is bi-invariant.

Proof.

We have that, for any choice of π and σ, SC⁢(π,σ)=c⁢(π⁢σ−1)n. Since any two conjugate permutations have the same cycle type, the function π↦c⁢(π)n is a class function, and the result follows from Lemma 21. ◀

Definition 23 (Bi-invariant Distribution over Functions).

We will say that a distribution ℋ over functions from 𝕊n into some set 𝒴 is bi-invariant if the function Pℋ⁢(⋅,⋅) is bi-invariant.

We now show that when studying the minimum achievable distortion for (𝕊n,SC), any LSH family can be assumed to be bi-invariant.

Lemma 24.

Suppose there exists a distribution ℋ over functions from 𝕊n into a finite set 𝒴 that Δ-approximates (𝕊n,SC), then there exists a bi-invariant distribution ℋ′ that Δ-approximates (𝕊n,SC).

Proof.

We construct ℋ′ by pre-composing the elements of ℋ with random left and right permutations: define a function h′∼ℋ′ as h′⁢(π)=h⁢(α⁢π⁢β), where h is drawn from ℋ and α,β are drawn uniformly and independently from 𝕊n. We first show that ℋ′ Δ-approximates (𝕊n,SC). For every choice of π,σ∈𝕊n, we have:

Prh′∼ℋ′⁡[h′⁢(π)=h′⁢(σ)] =𝔼α,β∼𝕊n⁢[Prh∼ℋ⁡[h⁢(α⁢π⁢β)=h⁢(α⁢σ⁢β)]]
≤𝔼α,β∼𝕊n⁢[SC⁢(α⁢π⁢β,α⁢σ⁢β)]
=Lemma 22⁢𝔼α,β∼𝕊n⁢[SC⁢(π,σ)]=SC⁢(π,σ),

where the first inequality uses that ℋ Δ-approximates (𝕊n,SC). Similarly:

Prh′∼ℋ′⁡[h′⁢(π)=h′⁢(σ)] =𝔼α,β∼𝕊n⁢[Prh∼ℋ⁡[h⁢(α⁢π⁢β)=h⁢(α⁢σ⁢β)]]
≥𝔼α,β∼𝕊n⁢[1Δ⋅SC⁢(α⁢π⁢β,α⁢σ⁢β)]
=Lemma 22⁢𝔼α,β∼𝕊n⁢[1Δ⋅SC⁢(π,σ)]=1Δ⁢SC⁢(π,σ),

Showing that indeed ℋ′ Δ-approximates (𝕊n,SC). Finally, we verify that Pℋ′ is bi-invariant. For any π,σ∈𝕊n and any left multiplier τ1 and right multiplier τ2:

Pℋ′⁢(τ1⁢π⁢τ2,τ1⁢σ⁢τ2)=𝔼α,β∼𝕊n⁢[Pℋ⁢(α⁢τ1⁢π⁢τ2⁢β,α⁢τ1⁢σ⁢τ2⁢β)].

Because α and β are drawn uniformly from the group, the products α′=α⁢τ1 and β′=τ2⁢β are also uniformly distributed. Thus, the expectation is identical to 𝔼α′,β′⁢[Pℋ⁢(α′⁢π⁢β′,α′⁢σ⁢β′)]=Pℋ′⁢(π,σ), completing the proof. ◀

Note also that, by Lemma 4, Pℋ′ is PSD and it is therefore a bi-invariant PSD kernel.

Recall that each partition λ⊢n is associated with a distinct irreducible representation Sλ of 𝕊n, we denote by χλ:𝕊n→ℂ its character, and by dλ∈ℕ its dimension.

Lemma 25.

Any bi-invariant PSD kernel P on 𝕊n can be written as a convex combination of normalized characters of irreducible representations of 𝕊n as follows:

∀σ,π∈𝕊n:P(σ,π)=∑λ:λ⊢nwλχλ⁢(σ⁢π−1)dλ,

where wλ≥0 and ∑λwλ=1.

Proof.

Let ϕ:𝕊n→ℝ be the class function satisfying:

ϕ⁢(σ⁢π−1)=P⁢(σ,π),

the existence of which is guaranteed by Lemma 21. By a result of Kondor [14, Corollary 4.5.5222We remark that Kondor’s result is stated in terms of what he refers to as “Positive Definite” kernels, which are, in reality, positive semidefinite kernels, as he himself explains earlier in the thesis.], since ϕ is PSD, we have:

ϕ=∑λ⊢naλ⋅χλ, (10)

for some choice of {aλ}λ⊢n, where each aλ∈ℝ≥0.

In particular:

1=P⁢(id,id)=ϕ⁢(id)=∑λ⊢naλ⋅χλ⁢(id)=∑λ⊢naλ⋅dλ,

where we use that χλ⁢(id)=dλ. Letting wλ:=aλ⋅dλ, together with Equation (10) completes the proof. ◀

For our asymptotic bounds, it is necessary to isolate the trivial representation (n), where χ(n)⁢(⋅)=1 and d(n)=1 and the sign representation (1n), where χ(1n)⁢(σ)=sgn⁡(σ) and d(1n)=1. Thus, it is helpful to write

P⁢(id,σ)=w0+wsgn⋅sgn⁡(σ)+∑λ≠(n),(1n)wλ⁢χλ⁢(σ)dλ. (11)

For a permutation σ∈𝕊n, the fixed-point count is defined as fix⁢(σ)=|{i∈[n]∣σ⁢(i)=i}|, i.e., the number of length-1 cycles. A derangement is a permutation σ that moves all elements, i.e., fix⁢(σ)=0. For any σ∈𝕊n, we also define the value supp(σ) as n−fix⁢(σ). We recall the following result.

Theorem 26 ([18]).

There exist absolute constants φ>0 and 0<q<1 such that for any partition λ=(λ1,…,λk)⊢n, any n≥4 and any permutation σ∈𝕊n:

|χλ⁢(σ)dλ|≤(max⁡{λ1n,kn,q})φ⋅supp(σ).

Theorem 26 allows us to prove the following.

Lemma 27.

There exist absolute constants φ>0 and 0<q<1 such that for any n≥4, any partition λ=(λ1,λ2,…,λk)⊢n, and any derangement σ∈𝕊n,

|χλ⁢(σ)dλ|≤e−φ⋅α,

where α=min⁡{n−λ1,n−k,(1−q)⁢n}.

Proof.

Since σ is a derangement, fix⁢(σ)=0; therefore supp(σ)=n−fix⁢(σ)=n. Furthermore, from the definition of α, we have:

max⁡{λ1n,kn,q}=1−αn.

Substituting these into the bound from Theorem 26 yields:

|χλ⁢(σ)dλ|≤(1−αn)φ⁢n≤e−φ⋅α.

◀

Lemma 28 (Theorem 1.2 (i) from [15], paraphrased).

For any derangement σ∈𝕊n and any partition λ⊢n:

|χλ⁢(σ)dλ|≤1dλ1/2−o⁢(1).
Lemma 29.

For any partition λ=(λ1,…,λk)⊢n with λ1≥1112⋅n, it holds that: dλ≥(n2⁢(n−λ1))n−λ1

Proof.

Let γ=n−λ1. By the hook length formula (see the appendix of the full version of the paper), we have:

dλ=n!∏h⁢(i,j) ≥n!(n−2⁢γ)!⋅nγ⋅γγ
=n⁢⋯⁢(n−2⁢γ+1)nγ⁢γγ
=nn⁢⋯⁢n−γ+1n⋅(n−γ)⁢⋯⁢(n−2⁢γ+1)γγ
≥(n−γ+1n)γ⋅(n−2⁢γ+1γ)γ
≥(n2−6⋅n⋅γγ⋅n)γ
=(nγ−6)γ
=(nγ⁢(1−6⁢γn))γ
≥(n2⁢γ)γ,

where the last inequality used the fact that γ≤n12. ◀

Lemma 30.

Consider any sufficiently large n, any derangement σ∈𝕊n, and let P be a bi-invariant PSD kernel. Let:

P⁢(τ,π)=∑λ⊢nwλ⁢χλ⁢(τ⁢π−1)dλ,

be the decomposition guaranteed by Lemma 25, then:

|∑λ⊢nλ≠(n),(1n)wλ⁢χλ⁢(σ)dλ|≤Cn,

for some constant C.

Proof.

We have:

|∑λ⊢nλ≠(n),(1n)wλ⁢χλ⁢(σ)dλ|≤maxλ⊢nλ≠(n),(1n)⁡|χλ⁢(σ)dλ|⁢∑λ⊢nλ≠(n),(1n)wλ≤maxλ⊢nλ≠(n),(1n)⁡|χλ⁢(σ)dλ|,

where we first apply Hölder’s inequality on ℓ∞ and ℓ1 and then we use the fact that ∑λ⊢nwλ=1, as well as the non-negativity of the wλs. We now give an upper bound for the right-hand side. Let φ and q be the constants given by Lemma 27. Let λ=(λ1,…,λk)⊢n, and let α=min⁡{n−λ1,n−k,(1−q)⁢n}. Since λ≠(n),(1n), we have min⁡{n−λ1,n−k}≥1. We obtain an upper bound by considering five possible cases for the value of α.

Case 1:

α=(1−q)⁢n. Using Lemma 27, we have:

|χλ⁢(σ)dλ|≤e−φ⋅α=e−Θ⁢(n)=o⁢(1n).

For the rest of the proof we will assume that α=n−λ1≥1. This is without loss of generality, since, for any partition that does not satisfy this condition (i.e., for which α=n−k), its transpose partition does satisfy it, and the values of |χλ⁢(σ)dλ| are the same for the two partitions.

Case 2:

α≥1φ⁢ln⁡n. Using Lemma 27 we have:

|χλ⁢(σ)dλ|≤e−φ⋅α≤1n.
Case 3:

3≤α<1φ⁢ln⁡n. Using Lemma 28 and Lemma 29 and recalling that α=n−λ1, and that therefore λ1=n−α>n−1φ⁢ln⁡n≥1112⁢n for sufficiently large n, we obtain:

|χλ⁢(σ)dλ|≤(1dλ)1/2−o⁢(1)≤(2⁢αn)α⁢(12−o⁢(1))≤((2/φ)⋅ln⁡(n)n)3/2−o⁢(1)=O⁢(1n),

where we use that α≥3 and α<O⁢(log⁡n).

Case 4:

α=1. In this case, the only partition is λ=(n−1,1), corresponding to the standard representation, which has dimension n−1. Its character is known to satisfy χλ⁢(π)=fix⁢(π)−1 (See [19, Example 2.3.8]). Since σ is a derangement, fix⁢(σ)=0, and the character χλ⁢(σ)=−1. We then have:

|χλ⁢(σ)dλ|=|−1n−1|=O⁢(1n).
Case 5:

α=2. In this case, the only two partitions are λ=(n−2,2) and μ=(n−2,1,1).

By (19) in Example 32 in the appendix of the full version of the paper, we can write the character of the permutation module M(n−2,2) as the sum of irreducible characters as follows:

χM(n−2,2)=χ(n−2,2)+χ(n−1,1)+χ(n).

By equation (17) in the appendix of the full version of the paper, this equation becomes:

cycle2⁢(π)+(fix⁢(π)2)=χ(n−2,2)⁢(π)+fix⁢(π)−1+1,

for all π∈𝕊n, where cycle2⁢(π) is the number of length-two cycles in the cycle decomposition of π. And hence:

χ(n−2,2)⁢(π)=cycle2⁢(π)+(fix⁢(π)2)−fix⁢(π),

for all π∈𝕊n.

Similarly, by Equation (20) in Example 32 in the appendix of the full version of the paper, we can write the character of the permutation module M(n−2,1,1) as:

χM(n−2,1,1)=χ(n−2,1,1)+χ(n−2,2)+2⁢χ(n−1,1)+χ(n).

By Equation (18) in that same appendix, this equation becomes:

fix⁢(π)⁢(fix⁢(π)−1)=χ(n−2,1,1)+χ(n−2,2)+2⁢(fix⁢(π)−1)+1

for all π∈𝕊n, which gives:

χ(n−2,1,1)=1−cycle2⁢(π)+fix⁢(π)⁢(fix⁢(π)−3)2

for all π∈𝕊n. Since σ is a derangement and fix⁢(σ)=0, we have:

χ(n−2,2)⁢(σ)=cycle2⁢(σ),

and:

χ(n−2,1,1)⁢(σ)=1−cycle2⁢(σ).

By Example 21 in the appendix of the full version of the paper: dλ=n⁢(n−3)/2 and dμ=(n−1)⁢(n−2)/2. Putting things together, we have that:

|χλ⁢(σ)dλ| =2⋅cycle2⁢(σ)n⁢(n−3)≤nn⁢(n−3)=1n−3=O⁢(1n),

and:

|χμ⁢(σ)dμ|=2⋅(cycle2⁢(σ)−1)(n−1)⁢(n−2)≤n(n−1)⁢(n−2)=O⁢(1n).

This completes the proof of Lemma 30. ◀

We can now complete the proof of Theorem 19.

Proof of Theorem 19.

Let n≥6 be a large enough integer so that Lemma 30 holds. Let ℋ be a distribution that Δ-approximates (𝕊n,SC). Without loss of generality, by Lemma 24, we can assume that Pℋ is a bi-invariant PSD kernel.

We let σ∗ be a derangement with Θ⁢(n) cycles and π∗ be a derangement with O⁢(1) cycles and having the same sign as σ∗. We explicitly define these permutations expressing them in their cycle decomposition. If n is even, we let:

σ∗:=∏i=1n/2(2⁢i−1,2⁢i),

and observe that c⁢(σ∗)=n/2. If instead n is odd, we define:

σ∗:=(1,2,3)⁢∏i=2n−12(2⁢i,2⁢i+1),

and observe that c⁢(σ∗)=(n−1)/2 and σ∗ can be decomposed in (n+1)/2 transpositions. Now, if n is even and sgn⁡(σ∗)=1 or if n is odd and sgn⁡(σ∗)=−1, we define:

π∗=(1,2,…,n−3)⁢(n−2,n−1,n),

and note that sgn⁡(π∗)=sgn⁡(σ∗) since it can be decomposed into n−2 transpositions. If instead n is even and sgn⁡(σ∗)=−1 or if n is odd and sgn⁡(σ∗)=1, we define:

π∗=(1,2,…,n),

and note that sgn⁡(π∗)=sgn⁡(σ∗) since it can be decomposed into n−1 transpositions.

Observe that, since n≥6:

SC⁢(id,σ∗)≥(n−1)/2n≥13andSC⁢(id,π∗)≤2n.

Since ℋ Δ-approximates (𝕊n,SC), we have:

Pℋ⁢(id,π∗)≤SC⁢(id,π∗)≤2n.

Plugging this into (11), and letting C be the constant in the statement of Lemma 30:

w0+wsgn−Cn ≤Lemma 30⁢w0+wsgn⋅sgn⁡(π∗)+∑λ⊢nλ≠(n),(1n)wλ⁢χλ⁢(π∗)dλ⁢=(11)⁢Pℋ⁢(id,π∗)≤2n,

giving:

w0+wsgn≤2+Cn. (12)

Again applying Equation 11 and Lemma 30, we have:

Pℋ⁢(id,σ∗)⁢≤(11),Lemma 30⁢w0+wsgn+Cn⁢≤(12)⁢2+2⁢Cn.

On the other hand:

Pℋ⁢(id,σ∗)≥1Δ⁢SC⁢(id,σ∗)=13⁢Δ.

Combining the last two equations yields:

Δ≥n6⁢(1+C),

completing the proof. ◀

8 Conclusions and Open Questions

Our work shows that the Ulam similarity enjoys sublinear LSH distortion whereas the Cayley similarity does not. An obvious open problem is to close the glaring yet tantalizing gap between the upper bound (n/log⁡n) and the lower bound (Ω⁢(n0.12)) for the Ulam similarity; our current belief is that the correct LSH distortion bound is Θ~⁢(n). Improving the base case (Proposition 16) is a natural direction, though there are computational limitations to finding a larger and better base instance. While it seems possible to improve our upper bound to O~⁢(n/log⁡n), going beyond this to O~⁢(n1−Ω⁢(1)) might require an entirely new approach. Extending our results to other permutation similarities such as reversal is another interesting direction; our current lower bound techniques seem inadequate for the block reversal similarity, for which we conjecture an Ω⁢(n) lower bound.

LLM Usage

The Ulam upper bound was obtained after weeks of interaction with and help from an LLM; the LLM-generated proof was hand-verified and somewhat simplified. The solver for the base case of the Ulam lower bound was written by an LLM; the instance itself was hand-verified. The high-level approach of using representation theory, in particular, Roichman’s Theorem and derangements, to obtain the Cayley lower bound was suggested by an LLM (after the initial attempts to extend Ulam lower bound proof approach to Cayley failed). All the final proofs were written and verified by the authors.

References

  • [1] Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. CACM, 51(1):117–122, 2008. doi:10.1145/1327452.1327494.
  • [2] Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer. Overcoming the l1 non-embeddability barrier: algorithms for product metrics. In SODA, pages 865–874, 2009. doi:10.1137/1.9781611973068.94.
  • [3] Alexandr Andoni and Robert Krauthgamer. The computational hardness of estimating edit distance. SICOMP, 39(6):2398–2429, 2010. doi:10.1137/080716530.
  • [4] Andrei Z Broder. On the resemblance and containment of documents. In SEQUENCES, pages 21–29, 1997. doi:10.1109/SEQUEN.1997.666900.
  • [5] Andrei Z. Broder, Moses Charikar, Alan M. Frieze, and Michael Mitzenmacher. Min-wise independent permutations. JCSS, 60(3):630–659, 2000. doi:10.1006/JCSS.1999.1690.
  • [6] Moses Charikar. Similarity estimation techniques from rounding algorithms. In STOC, pages 380–388, 2002. doi:10.1145/509907.509965.
  • [7] Moses Charikar, Ofir Geri, Michael P. Kim, and William Kuszmaul. On estimating edit distance: Alignment, dimension reduction, and embeddings. In ICALP, pages 34:1–34:14, 2018. doi:10.4230/LIPIcs.ICALP.2018.34.
  • [8] Moses Charikar and Robert Krauthgamer. Embedding the Ulam metric into l1. Theory Comput., 2(11):207–224, 2006. doi:10.4086/TOC.2006.V002A011.
  • [9] Flavio Chierichetti, Ravi Kumar, Alessandro Panconesi, and Erisa Terolli. On the distortion of locality sensitive hashing. SICOMP, 48(2):350–372, 2019. doi:10.1137/17M1127752.
  • [10] Persi Diaconis. Group Representations in Probability and Statistics. Inst. Math. Stat., 1988.
  • [11] Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Similarity search in high dimensions via hashing. In VLDB, pages 518–529, 1999. URL: http://www.vldb.org/conf/1999/P49.pdf.
  • [12] Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In STOC, pages 604–613, 1998. doi:10.1145/276698.276876.
  • [13] Piotr Indyk, Rajeev Motwani, Prabhakar Raghavan, and Santosh S. Vempala. Locality-preserving hashing in multidimensional spaces. In STOC, pages 618–625, 1997. doi:10.1145/258533.258656.
  • [14] Imre Risi Kondor. Group Theoretical Methods in Machine Learning. Columbia U., 2008.
  • [15] Michael Larsen and Aner Shalev. Characters of symmetric groups: sharp bounds and applications. Invent. Math., 174(3):645–687, 2008.
  • [16] Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. Multi-probe LSH: efficient indexing for high-dimensional similarity search. In VLDB, pages 950–961, 2007. URL: http://www.vldb.org/conf/2007/papers/research/p950-lv.pdf.
  • [17] Paul Renteln. A combinatorial proof of a symmetric group character involution. The American Mathematical Monthly, 130(9):855–858, 2023. doi:10.1080/00029890.2023.2242042.
  • [18] Yuval Roichman. Upper bound on the characters of the symmetric groups. Invent. Math., 125:451–485, 1996.
  • [19] Bruce Sagan. The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions. Springer Science & Business Media, 2001.
  • [20] Venu Satuluri and Srinivasan Parthasarathy. Bayesian locality sensitive hashing for fast similarity search. Proc. VLDB Endow., 5(5):430–441, 2012. doi:10.14778/2140436.2140440.