Permutation Arrays Under the Chebyshev Distance

• Chebyshev distance is motivated by multilevel flash-memory recharging and error-correction concerns under a noisy channel with independent, zero-mean Gaussian noise at each position.The paper denotes this distance by dmax and defines it as the maximum absolute difference between corresponding permutation entries.Source: §1 · pp. 1–2
• Earlier work studied permutation correlations using Hamming distance and transpositions,, Spearman’s rank correlation, and Kendall’s tau.Source: §1 · pp. 1–2
• The paper gives several permutation-array constructions, some with efficient decoding, and also considers encoding vectors into permutations.Source: §1 · p. 2

• The paper writes [n] for {1, . . . , n}, Sn for the permutations of [n], and Xn for n-tuples with elements from X.Source: §2 · p. 2
• An (n, d) permutation array is a subset of Sn whose distinct elements have Chebyshev distance at least d; its elements are also called code words.Source: §2 · p. 2
• P(n, d) denotes the maximal size of an (n, d) array, while V(n, d) counts permutations within Chebyshev distance d of the identity, a count equal for any center permutation.The section states that bounds on P(n, a) and V(n, d) are considered later.Source: §2 · p. 2

3.1 An explicit construction

• When n = ad + b with 0 ≤ b < d, the explicit residue-class construction is an (n,d) PA and is much larger than 2^(n−d) when 2d < n.For n=30 and d=2, the passage reports |C|/2^(n−d) ≈ 6.37 × 10^15.Source: §3.1 · pp. 2–3
• For d ≥ 2t + 1, the explicit construction corrects errors of size up to t in each coordinate by choosing the nearest value congruent to that coordinate modulo d.Source: §3.1 · p. 3

3.2 First recursive construction

• The second recursive construction yields P(rn, rd) ≥ P(n, d)^r by combining r code words into longer code words.The construction produces an (rn,rd) PA whose size is the rth power of the original array's size.Source: §3.2 · p. 3

3.3 Second recursive construction

• For n ≤ 2d, the second recursive construction extends an (n,d) PA of size M to an (n+1,d+1) PA of the same size.A related construction gives an (n+1,d) PA of size tM under its stated conditions.Source: §3.3 · p. 4
• Example 1’s explicit construction implies P(2a, 2) >= (a!)^2; in Example 2, combining Theorem 5 with search improves this bound, yielding P(7, 2) >= 582.Source: §3.3 · p. 5
• P(d + 1, d) = 3 for d ≥ 2, while for fixed r the size P(d+r,d) is bounded by a constant once d is sufficiently large.The general constants supplied by Theorem 7 may be weak; for r=1 it gives c1 ≤ 8 and d1 ≤ 8, while Theorem 8 establishes the exact value.Source: §3.3 · pp. 5, 8

3.4 Encoding/decoding of some PA constructed by the second recursive construction

• For binary vectors, the construction maps into an (n,d) PA of size 2^(n−d), and its recursive encoding and decoding correct errors of size at most (d−1)/2.At each prefix of a permutation, the next element has two possibilities, designated “smaller” and “larger”; the construction also extends to q-ary vectors.Source: §3.4 · pp. 8, 10

4.1 General bounds

• The greedy construction gives P(n, d) ≥ n!/V(n, d −1), by covering S_n with radius-(d−1) spheres when the algorithm stops.It repeatedly selects a permutation at distance at least d from those already chosen.Source: §4.1 · p. 10
• For even d with d < n ≤ 2d, Theorem 11 gives P(n, d) ≤ (n + 1)!/V(n + 1, d/2), a bound reported as stronger than the ordinary Hamming bound in tested cases.The section also gives the ordinary Hamming-type upper bound using disjoint spheres of radius floor((d−1)/2).Source: §4.1 · pp. 10–11
• Theorem 6 can be applied repeatedly before Theorem 10; the text reports the best bounds among these choices at r = 1 for even d and r = 0 for odd d.The repeated-bound statement applies for all r ≥ 0.Source: §4.1 · p. 11
• The Chebyshev-radius ball size V(n, d) equals the permanent of A(n, d), and for fixed d it satisfies a linear recurrence in n.The matrix is defined through the allowed index offsets; the recurrence results are attributed to, with explicit cases attributed to Lehmer and Kløve.Source: §4.1 · pp. 11–12
• For A(n, d), the largest recurrence root satisfies µ_d ≤ [(2d + 1)!]^(1/(2d+1)); the section notes µ_d/(2d + 1) ≈ 1/e for large d.Table 1 presents µ_d and this upper bound.Source: §4.1 · p. 12, Table 1 · p. 12

4.2 Table of bounds on P(n, d)

• For n = 8 and d = 5, the greedy algorithm found a permutation array of size 26.Most lower bounds in Table 2 were found by the greedy algorithm; some other lower bounds use Theorem 6, while upper bounds use Theorem 10 or 11.Source: §4.2 · p. 13, Table 2 · p. 13

5 Conclusion

• The paper gives multiple constructions of permutation arrays under Chebyshev distance, some with efficient decoding algorithms.Source: §5 · p. 13
• It considers an explicit mapping from vectors to permutations with efficient encoding and decoding.Source: §5 · p. 13
• It gives bounds on the size of permutation arrays under Chebyshev distance.Source: §5 · p. 13