A Class of Shift-Invariant Permutations and Their Algebraic Structure

II. Preliminaries

• A mapping is shift-invariant when it commutes with the cyclic shift S, which rotates the coordinates modulo n.The component-wise product is compatible with this shift: S(x ⊙ y) = S(x) ⊙ S(y).Source: §II · p. 3
• A landscape function is specified by disjoint offset sets R and T, with a landscape string encoding their local coordinate roles.The condition n > m + k ensures offsets in [−k, m] are distinct modulo n; the classical χ transformation is one example.Source: §II · p. 3
• A landscape is quasi-conserved with special index q when S^δℓ ⊙ ℓ = 0 for every support offset δ other than q.Conservation requires this equality for every offset in the support.Source: §II · p. 3
• Under n > m + k, quasi-conservation is characterized by an offset congruence for each δ in the support other than q.For each such δ, some r in R and t in T satisfy r + δ ≡ t or t + δ ≡ r modulo n.Source: §II · p. 3
• The paper assumes R and T are nonempty, q ≠ 0, and 0 is outside the landscape support.Under quasi-conservation, q ≠ 0 implies 0 is outside the support.Source: §II · p. 3
• Complementing the input preserves quasi-conservation and the polynomial composition property, while exchanging R and T moves q from R to T.The complemented mappings satisfy γ̄_j = γ_j ◦ J for j ≥ 1.Source: §II · p. 4

A. Polynomial composition of functions and quasi-conservation of related landscapes

• This subsection directly proves on F_2^n an equivalence that Kriepke stated without proof in Theorem 3.9 [13].Source: A. Polynomial composition of functions… · p. 4
• Theorem 3.2 establishes that, under n > max{2m + k, 2k + m}, quasi-conservation with special index q is equivalent to the polynomial composition property of {γ_j}.The condition uses k and m such that the landscape’s sets R and T lie in [−k, m].Source: A. Polynomial composition of functions… · p. 4
• The condition n > max{2m + k, 2k + m} cannot generally be replaced by n > m + k; Example 3.5 gives n = 6 with k = 1 and m = 3.Its landscape has R = {−1, 2}, T = {3}, and special index q = 3.Source: A. Polynomial composition of functions… · p. 8

• For supp(ℓ) \ {3} = {−1, 2}, ℓ is quasi-conserved on F6, yet γ1(x + γ1(x)) = (1, 0, 0, 0, 0, 0) ≠ 0 = γ1(x) + γ2(x), so the polynomial composition property fails.Source: A. Polynomial composition of functions… · p. 8

B. Long-term behavior of the sequence {γj}j≥1

• When C is nonempty, γ_j first becomes zero at j0 = min_(r,t)∈C j(r,t), with separate formulas for t≠q and t=q.For t≠q, j(r,t)=1+min{μ∈[1,d−1]: r−t≡±μq (mod n)}; for t=q, j(r,q)=min{ν∈[2,d−1]: r≡νq (mod n)}.Source: B. Long-term behavior of the sequence… · p. 8
• When C is empty, γ_j never vanishes and becomes periodic from the first stabilization index j1, with least eventual period d.From j1 onward, γ_(j+1)=S_qγ_j; d is the least positive integer with dq≡0 (mod n).Source: B. Long-term behavior of the sequence… · pp. 9–10
• The indices are bounded by d: j0≤d when C is nonempty, and j1≤d when C is empty.Here d is the least positive integer satisfying dq≡0 (mod n).Source: B. Long-term behavior of the sequence… · pp. 8, 10
• If C is nonempty, γ_0 through γ_(j0−1) are linearly independent; if C is empty, γ_0 through γ_(j1+d−1) are linearly independent.These ranges give independence up to the first relation in the two respective cases.Source: B. Long-term behavior of the sequence… · p. 10

C. Shift-invariant permutations and their algebraic structure

• Composition in the mapping monoid corresponds to multiplication in a quotient ring, and the permutation elements correspond to its units.The monoid isomorphism restricts to a group isomorphism between the permutation elements and the unit group.Source: C. Shift-invariant permutations and… · p. 11
• When C is nonempty, every element of M is a unit and G*=G; when C is empty, permutation membership requires a unit in the quotient ring.For C empty, the supplied proof reduces the test to coprimality with 1 + z^d after checking coprimality with z^j1.Source: C. Shift-invariant permutations and… · p. 12
• Theorem 3.10 gives quotient-ring formulas for inverses, iterates, and composition orders of permutations in G*.Its inverse and iterate formulas specify coefficients of the corresponding mappings.Source: C. Shift-invariant permutations and… · p. 12
• For C nonempty, the order of a nonidentity F is a power of two, with the least exponent ν satisfying bj·2^ν ≥ j0.For C empty, the order is also a power of two and the criterion additionally requires ρ·2^ν ≥ d.Source: C. Shift-invariant permutations and… · p. 13
• The applications construct explicit shift-invariant permutations from binomials and trinomials in Q and derive their orders, inverses, and iterates.The section also discusses fixed points of the constructed mappings.Source: §IV · p. 13

A. Permutations via permutation binomials in Q

• βh is a permutation if and only if C is nonempty.Under this condition, the section studies h from 1 to j0 − 1.Source: A. Permutations via permutation… · p. 13
• For iterates βh^(2^j), the section gives a fixed-point criterion: γ_(2^j h)(x) = 0.This criterion applies for j ≥ 0 with 2^j h < j0.Source: A. Permutations via permutation… · p. 13
• The cited passage states that βh is an involution if and only if 2h ≥ j0, giving the exact threshold condition for involutivity without additional qualifications in that statement.Source: A. Permutations via permutation… · p. 13
• The corollary gives three landscape conditions under which F is a permutation exactly when some r ∈ R and t ∈ T satisfy r ≡ t (mod gcd(n, q)).The conditions assume n > max{2m + k, 2k + m}.Source: A. Permutations via permutation… · p. 14
• For the three example mappings, ord(F1) = 2 and ord(F2) = ord(F3) = 4.F1 is an involution, so its inverse is itself.Source: A. Permutations via permutation… · p. 14

• κ_u = id + γ_u + γ_2u is a permutation exactly when 1 + z^u + z^2u is a unit in Q.Source: B. Permutations via permutation… · p. 14
• Proposition 4.4 gives iterates, orders, and inverses for κ_u, with the allowed u range depending on whether C is empty.Source: B. Permutations via permutation… · p. 14
• For u = 1, F = id + γ_1 + γ_2 is a permutation exactly when C ≠ ∅ or 3 ∤ d.Source: B. Permutations via permutation… · p. 15
• Under the three stated offset-set conditions, F is a permutation iff some r ∈ R and t ∈ T satisfy r ≡ t mod gcd(n, q), or 3 ∤ d.Source: B. Permutations via permutation… · p. 15
• Example 4.6 supplies explicit shift-invariant permutations for each of the three offset-set cases.Source: B. Permutations via permutation… · p. 15
• ord(F_4) = ord(F_6) = 4, while ord(F_5) = 60 in the three worked examples.The stated calculation for F_5 is lcm(4, 15) = 60.Source: B. Permutations via permutation… · p. 16
• The representative tables list landscapes with |supp(ℓ)| ≤ 4 and supp(ℓ) ⊆ [−4, 4], with permutation criteria expressed as conditions on n.Source: C. Representative families of… · p. 16
• For each mapping family, permutation dimensions are exactly those n divisible by none of its divisibility-minimal nonpermutation dimensions in ξ(F).The nonpermutation dimensions are closed under taking multiples.Source: C. Representative families of… · p. 16

• D contains the positive divisors g of q for which no r ∈ R and t ∈ T are congruent modulo g.Source: §2 · p. 16
• β_1 is a permutation exactly when no g ∈ D divides n; κ_1 is a permutation exactly when no 3^v3(q/g)+1g divides n for g ∈ D.Source: §2 · p. 16
• The tables’ ξ(β_1) and ξ(κ_1) entries denote divisibility-minimal dimensions where the respective mappings are not permutations.Source: §2 · p. 17
• For the example with R = {2}, T = {−1, 3, 4}, and q = 4, β_1 is a permutation iff 4 ∤ n, while κ_1 is one iff 12 ∤ n.Source: §2 · p. 17

V. Conclusion and Future Work

• The group of permutation elements in the generated monoid is isomorphic to the unit group of a quotient ring, enabling polynomial criteria and formulas for inverses, orders, and iterates.The quotient is Q = F2[z]/⟨p(z)⟩, with p(z) determined by the landscape.Source: §V · p. 17
• More than 100 representative shift-invariant permutation constructions are listed, including families studied previously in,,, –.The constructions specialize the results to mappings represented by binomials and trinomials in Q and give conditions on n for permutation behavior.Source: §V · p. 17
• For m + k < n ≤ max{2m + k, 2k + m}, whether quasi-conservation and polynomial composition are equivalent may vary across examples.Clarifying which functions in this dimension range have the polynomial composition property is identified as future work.Source: §V · p. 18
• Further directions include generalizing the recurrence or relaxing quasi-conservation while retaining a weaker algebraic structure under composition.The paper also proposes developing permutation criteria and methods for computing inverses and iterates in these settings.Source: §V · p. 18

Appendix Quasi-Conservation and Polynomial Composition on FZ

• When n > max{2m + k, 2k + m}, quasi-conservation and the polynomial composition property are equivalent for the landscapes and mapping sequences considered.The appendix establishes equivalence between their formulations on FZ and Fn under this dimension condition.Source: Appendix Quasi-Conservation and… · p. 20
• At n = max{2m + k, 2k + m}, the equivalence in Theorem A.1 can fail.The appendix supplies an example at this boundary, so the strict dimension condition cannot generally be weakened to equality.Source: Appendix Quasi-Conservation and… · p. 20
• The nonzero-special-index assumption is necessary: with q = 0, quasi-conservation need not imply the polynomial composition property.For R = {1}, T = {0}, the paper gives an input pattern for which the required composition identity fails.Source: Appendix Quasi-Conservation and… · p. 20
• If quasi-conservation holds on FZ with nonzero special index q, the polynomial composition property holds on Fn whenever n > m + k.This improves the stated bound when quasi-conservation is assumed on the two-sided sequence space.Source: Appendix Quasi-Conservation and… · p. 20