An interesting algebraic construction

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Consider the following constructive problem: Given prime $$$p$$$ and integer $$$k$$$, we need to construct operations $$$\oplus$$$ and $$$\otimes$$$ over the integers $$$0$$$ through $$$p^k-1$$$, such that for any $$$0\le x,y,z<p^k$$$, we have

$$$0\oplus x=x\oplus 0=x$$$ (additive identity)
$$$\exists r:a\oplus r=r\oplus a=0$$$ (additive inverse)
$$$1\otimes x=x\otimes 1=x$$$ (multiplicative identity)
$$$\exists r:a\otimes r=r\otimes a=1$$$ (multiplicative inverse)
$$$x\oplus y=y\oplus x$$$ (commutativity of addition)
$$$x\otimes y=y\otimes x$$$ (commutativity of multiplication)
$$$(x\oplus y)\oplus z=x\oplus(y\oplus z)$$$ (associativity of addition)
$$$(x\otimes y)\otimes z=x\otimes(y\otimes z)$$$ (associativity of multiplication)
$$$(x\oplus y)\otimes z=x\otimes z+y\otimes z$$$ (distributivity)

In other words, construct a field of size $$$p^k$$$.

The field $$$\mathbb Z_p$$$ are the integers modulo some prime $$$p$$$. How can we use this to construct a field of size $$$p^k$$$, where $$$k$$$ is some integer greater than $$$2$$$?

Consider some polynomial of degree $$$k$$$, $$$F(x)=a_0+a_1x+a_2x^2+\dots+a_{k-1}x^{k-1}+x^k$$$, such that $$$F(x)$$$ is irreducible modulo $$$p$$$, or that it has no nontrivial factors. What would happen if we introduce a new element $$$I$$$, that is defined to be a root of $$$F(x)$$$, much like how mathematicians introduced $$$i$$$ as a root of $$$x^2+1$$$?

By the definition of $$$I$$$, we must have that

$$$I^k+a_{k-1}I^{k-1}+\dots+a_2I^2+a_1I+a_0=0$$$

or equivalently

$$$I^k=-a_{k-1}I^{k-1}-\dots-a_2I^2-a_1I-a_0$$$

Hence, we can create a new field where elements are of the form $$$v_0+v_1I+v_2I^2+\dots+v_{k-1}I^{k-1}$$$, where $$$0\le v_i<p$$$. Addition is done term-wise, and multiplication is equivalent to convolution. Note that if after a multiplication there $$$I^k,I^{k+1},\dots,I^{2k-2}$$$ terms are nonzero, we can reduce them using $$$I^k=(P-a_{k-1})I^{k-1}+\dots+(P-a_2)I^2+(P-a_1)I+(P-a_0)$$$.

The number of elements in this field is obviously $$$p^k$$$, but how do we verify that it indeed is a field, and that for reducible $$$F(x)$$$ the resulting elements do not form a field?

Observe, that we can treat all elements of this field as polynomials in the ring $$$Z_p[x]$$$ with highest nonzero term of degree at most $$$k-1$$$ during operations, keeping in mind to reduce after a multiplication. But we can do better — during multiplication, because $$$I^k$$$ becomes $$$(P-a_{k-1})I^{k-1}+\dots+(P-a_2)I^2+(P-a_1)I+(P-a_0)$$$, the polynomials are taken modulo $$$x^k-\left((P-a_{k-1})I^{k-1}+\dots+(P-a_2)I^2+(P-a_1)I+(P-a_0)\right)$$$, or equivalently, $$$F(x)$$$! Now all that's left is to prove that $$$Z_p[x]/F(x)$$$, or all elements of $$$Z_p[x]$$$ modulo $$$F(x)$$$, forms a field.

Associativity, commutativity, additive identities ($$$0$$$), multiplicative identities ($$$1$$$), additive inverses, and distributivity are all readily obvious. What's left is to prove that every nonzero element of $$$Z_p[x]/F(x)$$$ has an inverse. In $$$A(x)B(x)\equiv 1\pmod{F(x)}$$$, $$$B(x)$$$ exists if and only if $$$A(x)$$$ is coprime to $$$F(x)$$$, using an extension of the extended Euclidean algorithm to polynomials. Because $$$F(x)$$$ is irreducible, it has no factors other than $$$1$$$ less than itself, so every nonzero element of $$$Z_p[x]/F(x)$$$ is coprime to $$$F(x)$$$ — note that this doesn't hold when $$$F(x)$$$ isn't irreducible!

Hence, we have proven that $$$Z_p[x]/F(x)$$$ is a field, and equivalently, the field we have constructed out of elements of the form $$$v_0+v_1I+v_2I^2+\dots+v_{k-1}I^{k-1}$$$ is a field.

I saw this problem on multiple sources, one of which is chapter 10 of Introductory Combinatorics, but I felt like I made some semi-interesting insights that I was proud of and wanted to share it with Codeforces :)

Have a nice day!

Comments (17)

Write comment?

box

3 years ago, # |

← Rev. 2 →

-22

Auto comment: topic has been updated by box (previous revision, new revision, compare).

Subscribe to Technoblade!

→ Reply

Monogon

+16

What's an example of a problem that involves these finite fields? How should one go about finding irreducible polynomials?

3 years ago, # ^ |

+27

There is a problem, as is, in Chinese, but I don't know if this has applications outside of this.. It can't be used for computations mod $$$p^k$$$ AFAIK because there is little to no relation between the inverses here and the inverses mod $$$p^k$$$.

A quick search about these irreducible polynomials reveals this, which claims the number of irreducible polynomials of degree $$$k$$$ is slightly less than $$$1/k$$$, and also gives a formula for counting the number of such polynomials. I guess you can randomly choose polynomials and then use Berlekamp's algorithm.

dpaleka

Sieve of Eratosthenes, if $$$k$$$ is small enough and you don't want to bother with factorizing?

adamant

← Rev. 3 →

Here's the problem: You're given $$$a_1, \dots,a_n$$$, compute the number of solutions to $$$\sqrt{a_1} \pm \dots \pm \sqrt{a_n} = 0$$$.

Here $$$a_i$$$ might be large, so to solve it you take them modulo $$$p$$$ and then take square roots in $$$GF(p^2)$$$.

To properly utilize field operations here you may consider the following variation: You're given $$$a_1,\dots,a_n$$$ and $$$b_1,\dots,b_m$$$. What is the number of solutions to $$$(\sqrt{a_1}\pm\dots\pm\sqrt{a_n})(\sqrt{b_1}\pm\dots\pm\sqrt{b_m})=1$$$.

The other example is that $$$GF(2^{2^n})$$$ is equivalent to nimbers.

Another example is this problem. It reduces to something like you're given $$$P(x)$$$ and you want to compute $$$P(1)P(\omega)\dots P(\omega^{n-1})$$$ modulo $$$10^9+7$$$ where $$$\omega^n=1$$$.

As you usually don't have an element with such property, you would need to extend the field you're working in. It may be done by computing everything modulo cyclotomic polynomial $$$\Phi_n(x)$$$ which is technically a finite field $$$GF(p^{\varphi(n)})$$$.

Note that it's the initial version of the solution, actual problem relies on computing the same value as a resultant of $$$P(x)$$$ and $$$x^n-1$$$, as it can be done with a better complexity.

slycelote

Wikipedia page on Galois fields has a section on explicit construction.

-is-this-fft-

I have used them a couple times when you need to calculate something modulo $$$p$$$, and the formulas you have derived require elements that don't exist.

Example 1. You can show that the game has a similar strategy to Nim except you use a "ternary" XOR instead of binary. I needed to calculate a convolution with this ternary XOR. You can do it in the same way as binary XOR, but instead of evaluating a polynomial in all points in {$$$1, -1$$$}$$$^n$$$ (the second roots of unity), you evaluate it in all points {$$$1, \omega, \omega^2$$$}$$$^n$$$ such that $$$\omega \ne 1$$$ and $$$\omega^3 = 1$$$ (the third roots of unity). The problem? No such $$$\omega$$$ exists in $$$\mathbb{Z}_{10^9 + 7}$$$:

$$$x^3 - 1 = (x - 1)(x^2 + x + 1)$$$

and the latter factor of degree $2$ is irreducible. So, we do this part of the calculation in $$$\mathbb{Z}_{10^9 + 7}[x] / (x^2 + x + 1)$$$.

Example 2. The editorial solution is some nice combinatorics, but mine is with generating functions. Consider generating function $$$\mathcal{D}(x)$$$, where the coefficient of $$$x^k$$$ is the sum of all beauties for a strip of length $$$k$$$ and with initially no barriers. Without going into too much detail, you can start adding new barriers from left to right iteratively. Anyway, long story short, it turns out that you need to work with rational functions of the form

$$$h(x) = \frac{f(x)}{x^3 - 2x^2 + 4x - 1}$$$

and that it would be extremely nice to use their partial fraction decomposition. That is --- to express $h(x)$ as

$$$h(x) = p(x) + \displaystyle \sum_{i = 1}^3 \frac{A_i}{g_i(x)}$$$

where $A_i$ are numbers and $$$g_i$$$ are linear polynomials. For these $$$g_i$$$ to exist, you need to factor $$$x^3 - 2x^2 + 4x - 1$$$ into linear polynomials, and $$$x^3 - 2x^2 + 4x - 1$$$ is yet again an example of an irreducible polynomial in $$$\mathbb{Z}_{10^9 + 7}$$$. So, we'll do this part of computation in $$$\mathbb{Z}_{10^9 + 7}[x] / (x^3 - 2x^2 + 4x - 1)$$$

Example 3: hypothetical version of 446C - DZY Loves Fibonacci Numbers over $$$10^9 + 7$$$ instead of $$$10^9 + 9$$$. The solution uses the formulas for Fibonacci numbers involving $$$\sqrt{5}$$$. The number $$$\sqrt{5}$$$ exists modulo $$$10^9 + 9$$$, but not modulo $$$10^9 + 7$$$, so we need to work in $$$\mathbb{Z}_{10^9 + 7}[x] / (x^2 - 5)$$$.

It's very similar to real and complex numbers. You may have some problem where your data is wholly real, but some part of calculation works out better in complex numbers — for example, you may need to use the Fourier transform. So, you'd do that calculation in the complex numbers. IIRC, this is why the complex numbers were invented in the first place: to solve cubics where the equation and solutions were real, but it was convenient to use these "imaginary" numbers during some step inbetween. In fact, it's the exact same thing: $$$\mathbb{C}$$$ is $$$\mathbb{R}[x]/(x^2 + 1)$$$.

+34

This year's Croatian IOI team selection had a problem Jelo using this trick.

You need to construct a large set of integers with distinct pairwise XORs -- more precisely, we need $$$2^{N}$$$ nonnegative integers less than $$$2^{2N}$$$, such that there are $$$\binom{2^N}{2}$$$ distinct XORs of pairs. It's related to research in Sidon sets.