Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

box's blog

By box, history, 4 years ago, In English

Consider the following constructive problem: Given prime p and integer k, we need to construct operations and over the integers 0 through pk1, such that for any 0x,y,z<pk, we have

  1. 0x=x0=x (additive identity)
  2. r:ar=ra=0 (additive inverse)
  3. 1x=x1=x (multiplicative identity)
  4. r:ar=ra=1 (multiplicative inverse)
  5. xy=yx (commutativity of addition)
  6. xy=yx (commutativity of multiplication)
  7. (xy)z=x(yz) (associativity of addition)
  8. (xy)z=x(yz) (associativity of multiplication)
  9. (xy)z=xz+yz (distributivity)

In other words, construct a field of size pk.


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

Consider some polynomial of degree k, F(x)=a0+a1x+a2x2++ak1xk1+xk, 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 x2+1?

By the definition of I, we must have that

Ik+ak1Ik1++a2I2+a1I+a0=0

or equivalently

Ik=ak1Ik1a2I2a1Ia0

Hence, we can create a new field where elements are of the form v0+v1I+v2I2++vk1Ik1, where 0vi<p. Addition is done term-wise, and multiplication is equivalent to convolution. Note that if after a multiplication there Ik,Ik+1,,I2k2 terms are nonzero, we can reduce them using Ik=(Pak1)Ik1++(Pa2)I2+(Pa1)I+(Pa0).

The number of elements in this field is obviously pk, 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 Zp[x] with highest nonzero term of degree at most k1 during operations, keeping in mind to reduce after a multiplication. But we can do better — during multiplication, because Ik becomes (Pak1)Ik1++(Pa2)I2+(Pa1)I+(Pa0), the polynomials are taken modulo xk((Pak1)Ik1++(Pa2)I2+(Pa1)I+(Pa0)), or equivalently, F(x)! Now all that's left is to prove that Zp[x]/F(x), or all elements of Zp[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 Zp[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!

  • Vote: I like it
  • +147
  • Vote: I do not like it

»
4 years ago, # |
Rev. 2   Vote: I like it -22 Vote: I do not like it

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

Subscribe to Technoblade!

»
4 years ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +27 Vote: I do not like it

    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.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +9 Vote: I do not like it

    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).

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Problem D from Petrozavodsk Winter 2023. Day 5: LOUD Enough Contest 2 (or The 2nd Universal Cup. Stage 5: Northern)

    sorry for necroposting ;(

»
4 years ago, # |
Rev. 2   Vote: I like it +34 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it +59 Vote: I do not like it

Isn't this taught in the first year of any decent university?

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

thank you M. box