Why is my equation not true on all elements?

73 Views Asked by At

Consider a finite field $F_{17}$. In this, $\omega = 4$ is the primitive $4$th root of unity.

So there is a subgroup $\Omega = \{1, \omega, \omega^2, \omega^3\}$

Consider a polynomial $f \in F_{17}[x]$

And a 2nd polynomial $t$ built from $f$ as

$t(1) = f(1)$ and $t(\omega^s) = \prod_{i=0}^s f(a)$ for $s = 1, \omega, \omega^2, \omega^3$

i.e.

$t(1) = f(1)$

$t(\omega) = f(1)\cdot f(\omega)$

$t(\omega^2) = f(1)\cdot f(\omega)\cdot f(\omega^2)$

$t(\omega^3) = f(1)\cdot f(\omega)\cdot f(\omega^2) \cdot f(\omega^3)$

Now I consider 2 cases with 2 different $f$ polynomials

Case 1) $f = 3x^2 + 4x + 11$

For this, I create $t$ as langrange interpolation of these points.

$points=[(\omega^0,f(\omega^0)),(\omega,f(\omega^0)*f(\omega)),(\omega^2,f(\omega^0)*f(\omega)*f(\omega^2)),(\omega^3,f(\omega^0)* f(\omega)*f(\omega^2)*f(\omega^3))]$

$t = 10x^3 + 3x^2 + 15x + 7$

I can express the $t$ polynomial in terms of $f$ as

$t(\omega \cdot x) = t(x) \cdot f(\omega \cdot x)$

In this case, this equation,

$t(\omega \cdot x) = t(x) \cdot f(\omega \cdot )$

holds for all $x \in \{1, \omega, \omega^2, \omega^3\}$

Case 2) $f = 3x^2 + 4x + 7$

Here, I get through lagrange interpolation

$t = 6x^3 + 13x^2 + 11x + 1$

For this pair of $f$ & $t$ however, this equation $t(\omega \cdot x) = t(x) \cdot f(\omega \cdot x )$ doesn't hold for all elements of $\Omega$. It holds for $1, \omega, \omega^2$,

but with $x = \omega^3$

$t(\omega\cdot x) = 14$

while

$f(\omega \cdot x) \cdot t(x) = 11$

I am unable to understand why it's not true in all cases.

Is there a better way to express the relation $t(\omega \cdot x) = t(x) \cdot f(\omega \cdot x )$ so that it holds at all points?

1

There are 1 best solutions below

3
On BEST ANSWER

Because you defined $t(1)=f(1)$ the relation $$t(\omega x)=t(x)f(\omega x)$$ can hold at $x=\omega^3$ only when $t(\omega^4)=t(\omega^3)f(\omega^4)$. Or, when $$ \begin{aligned} f(1)=t(1)=t(\omega^4)&=t(\omega\cdot\omega^3)\\ &=t(\omega^3)f(\omega^4)\\ &=f(1)f(\omega)f(\omega^2)f(\omega^3)f(\omega^4). \end{aligned} $$ Cancelling the factor $f(1)=f(\omega^4)$ you get the requirement $$ f(1)f(\omega)f(\omega^2)f(\omega^3)=1\qquad(*) $$ as a consequence.

Your first choice of $f$ satisfies $(*)$ but the second choice does not.