The lift #
Given an even m and a square-difference-free set B of polynomials of degree below m, the
lift is
L_m(B) = { V_s + P·R_r + Q·(b + s_∞ T^m + u T^{m+1}) : s ∈ S, r ∈ F_3^3, u ∈ F_3, b ∈ B },
a set of polynomials of degree below m + 8 with exactly 810 · |B| elements, again
square-difference-free.
Three features of the formula do the work. The values of a lifted polynomial at 0, 1, 2 are
s_0, s_1, s_2, because P and Q vanish there; its coefficient at T^{m+6} is s_∞, because
Q has degree 6 and no T^5 term; and the remaining freedom (r, u, b) is recovered from the
polynomial itself, which is what makes the parameter map injective. A square difference of two
lifted polynomials therefore has all four coordinates of s' - s in {0, 1}, so the code
property gives s = s'; what is left is a square difference inside B, which B does not have.
A parameter tuple (s, r, u, b): a word of the code, the coefficient vector of R, a scalar,
and an element of the base.
Equations
Instances For
The tail of a lifted polynomial, b + s_∞ T^m + u T^{m+1}: what the multiplier Q acts on.
Equations
- NaslundCounterexample.tail m p = p.2.2.2 + Polynomial.C (p.1 3) * Polynomial.X ^ m + Polynomial.C p.2.2.1 * Polynomial.X ^ (m + 1)
Instances For
The lift of one parameter tuple, V_s + P·R_r + Q·(b + s_∞ T^m + u T^{m+1}).
Equations
Instances For
The parameter set S × F_3^3 × F_3 × B.
Equations
Instances For
The lifted set L_m(B), the image of the parameter set under the lift.
Equations
Instances For
A tuple is a parameter exactly when its code word and its base element are.
There are 810 · |B| parameter tuples: 10 · 27 · 3 choices besides the base element.
Membership in the lifted set: the elements of L_m(B) are the lifts of parameter tuples.
The tail has degree below m + 2 when its base element has degree below m.
The degree bound: a lift of a tuple whose base element has degree below m has degree below
m + 8.
The value of a lifted polynomial at 0 is the code coordinate s_0.
The value of a lifted polynomial at 1 is the code coordinate s_1.
The value of a lifted polynomial at 2 is the code coordinate s_2.
The coefficient of the tail at T^m is the code coordinate s_∞: the base element does not
reach T^m and the term u T^{m+1} lies above it.
The coefficient of the tail at T^{m+1} is the scalar u: the base element does not reach
T^{m+1} and the term s_∞ T^m lies below it.
The top coordinate. When the base element has degree below m, the coefficient of a
lifted polynomial at T^{m+6} is the code coordinate s_∞: the part V_s + P·R_r has degree at
most 5 < m + 6; Q · b has degree below m + 6; Q · s_∞ T^m contributes s_∞ times the
leading coefficient of Q; and Q · u T^{m+1} would contribute u times the vanishing
coefficient [T^5] Q.
Evaluations and the top coefficient recover the code word from a lifted polynomial.
Injectivity of the lift on parameters. Two tuples with base elements of degree below m
that lift to the same polynomial are equal. No division algorithm is needed: equal outputs give
(V_s + P·R_r) - (V_s' + P·R_r') = Q · (tail' - tail), whose left side has degree below 6, so
both sides vanish; evaluating at 0, 1, 2 identifies the code words, cancelling P identifies
r, and comparing the coefficients at T^m and T^{m+1} identifies u and b.
The lift of a set of polynomials of degree below m has degree below m + 8.
A square difference of lifts from an even degree bound has a bounded-degree square root.
All four code coordinates of a square difference are squares, so the code words agree.
Equal code coordinates force the square root to vanish at every element of F_3.
The low-degree part vanishes, allowing cancellation of Q from a square difference.
A tail difference has odd degree unless its scalar coordinates agree.
The lift preserves square-difference-freeness for even m. If two lifted polynomials
differ by z^2, then the four coordinates of s' - s are squares in F_3, hence in {0, 1},
so the code property gives s = s'; then z vanishes on F_3, so z = P·w, the parts below
Q cancel, and w^2 = (b' - b) + (u' - u) T^{m+1}. A nonzero square has even natural degree,
while m + 1 is odd, so u' = u; and w^2 = b' - b forces w = 0 because B is
square-difference-free.