🔢 mathematics

Splitting sums of binary polynomials

This paper establishes that five is the minimum number of polynomials over $\mathbb{F}_2[x]$ required such that the sums of any two distinct polynomials in the set cannot all be expressed in the form $x^k(x+1)^{\ell}$ .

Original authors: Luis H. Gallardo

Published 2026-02-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Luis H. Gallardo

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are playing a game with numbers, but instead of using the usual numbers like 1, 2, 3, you are using a special "binary" world where the only rules are 0 and 1. In this world, adding 1 and 1 doesn't give you 2; it gives you 0 (because $1+1=0$ in binary math).

In this paper, the author, Luis Gallardo, is investigating a puzzle about polynomials (mathematical expressions like $x^2 + x + 1$ ) made of these 0s and 1s.

The Big Picture: The "Perfect Pair" Puzzle

To understand the paper, let's start with a simpler version using regular integers (whole numbers).

The Integer Puzzle:
Imagine you have a group of friends. You want to find a group where every possible pair of friends adds up to a "special number."

In the real world, a "special number" might be a power of 2 (like 2, 4, 8, 16, 32...).
Can you find 3 friends? Yes! Take -1, 3, and 5.
- $-1 + 3 = 2$ (Power of 2)
- $-1 + 5 = 4$ (Power of 2)
- $3 + 5 = 8$ (Power of 2)
Can you find 4 friends? No. Mathematicians have proven it's impossible to find 4 distinct integers where every pair sums to a power of 2.

The Polynomial Puzzle:
Now, Gallardo asks: "What if we do this same game, but with binary polynomials instead of integers?"

In this game:

The Players: Instead of integers, we have polynomials like $x$ , $x^2+1$ , or $x^3+x$ .
The "Special Numbers": Instead of powers of 2 ( $2^n$ $2^{n}$ ), the "special numbers" are polynomials that look like $x^k(x+1)^\ell$ .
- Think of $x$ and $(x+1)$ as the "building blocks" (like 2 is the building block for powers of 2).
- A "special sum" is any combination of these building blocks.
The Goal: Find a group of polynomials where every pair adds up to one of these "special numbers."

The Discovery: The Magic Number is 5

The paper solves the question: "How many polynomials can we have in our group before the game becomes impossible?"

Group of 2: Easy. You can always find two polynomials that add up to a special number.
Group of 3: Possible. The paper proves you can find three polynomials ( $a, b, c$ ) where $a+b$ , $a+c$ , and $b+c$ are all "special."
Group of 4: Possible, but very tricky. The paper shows that if you do find four, they must follow a very strict, rigid pattern (like soldiers marching in a perfect line). They can't just be random; they have to be related in a specific way.
Group of 5: Impossible. This is the main result. Gallardo proves that you cannot find 5 distinct binary polynomials where every single pair adds up to a "special number."

The Analogy: The "Social Network" of Shapes

Imagine you are building a social network where every person must be friends with everyone else.

The Rule: Two people can only be friends if their combined "shape" is a perfect rectangle (our "special number").
The Finding:
- You can easily find 3 people who are all friends with each other.
- You can find 4 people, but they have to be very specific types of people (like a family where everyone looks exactly alike).
- But you can never find 5 people who are all mutual friends under these rules. If you try to add a 5th person, the math forces a contradiction. It's like trying to fit a square peg into a round hole; the geometry of the binary world simply doesn't allow it.

How Did He Solve It?

Gallardo didn't just guess. He used a mix of:

Logical Deduction: He broke the problem down into smaller pieces, proving that if a group of 4 exists, it must look a certain way.
The "Divisor" Tool: He used a mathematical tool called $\sigma$ (sigma), which adds up all the "parts" (divisors) of a polynomial. This helped him spot patterns that regular algebra missed.
Computer Verification: For the final step (proving 5 is impossible), he used a computer to check thousands of possibilities quickly. The computer confirmed that no matter how you try to arrange 5 polynomials, at least one pair will fail the "special sum" test.

Why Does This Matter?

This might seem like a niche math puzzle, but it's actually about understanding the fundamental structure of numbers.

Integers and Polynomials are often treated as "twins" in math.
By solving this puzzle in the polynomial world, we learn more about how numbers behave in general.
It shows that even in a world with only 0s and 1s, there are hidden limits to how things can combine. Just like you can't build a house with 5 walls if the blueprint only allows for 4, you can't build a group of 5 polynomials that satisfy these specific rules.

In short: The paper proves that in the binary polynomial world, the "magic number" for this specific friendship game is 5. You can have groups of 2, 3, or even 4 (with strict rules), but the moment you try to make a group of 5, the math breaks down.

1. Problem Statement

The paper investigates a polynomial analogue of a classical problem in integer arithmetic concerning sums of powers of 2.

Integer Context: It is known that sets of distinct integers $\{a, b, c\}$ exist where all pairwise sums are powers of 2 (e.g., $\{-1, 3, 5\}$ ). However, M.S. Smith proved that no set of four distinct integers exists where all six pairwise sums are powers of 2.
Polynomial Context: The author translates this problem to the ring of binary polynomials, $\mathbb{F}_2[x]$ $F_{2} [x]$ .
- Analogy: The integer $2^k$ is analogous to the polynomial $x^k(x+1)^\ell$ . Here, $x$ and $x+1$ are the irreducible polynomials of smallest degree in $\mathbb{F}_2[x]$ , playing the role of the prime number 2.
- Definition: A polynomial $A \in \mathbb{F}_2[x]$ "splits over $\mathbb{F}_2$ " if it is of the form $x^k(x+1)^\ell$ for non-negative integers $k, \ell$ (not both zero).
- The Core Question: Given a set $S_m$ of $m$ distinct binary polynomials, can the sum of every pair of distinct elements in $S_m$ be a splitting polynomial? Specifically, what is the maximal size of such a set?

2. Methodology

The author employs a combination of elementary algebraic number theory over finite fields, combinatorial analysis of exponents, and computational verification.

Algebraic Tools:
- Divisor Sum Function ( $\sigma$ ): The paper utilizes the sum of divisors function $\sigma(A)$ in $\mathbb{F}_2[x]$ . Key properties used include multiplicativity for coprime polynomials and specific values for irreducible polynomials (e.g., $\sigma(x^k) = 1 + x + \dots + x^k$ ).
- Mersenne Polynomials: Defined as $A = x^a(x+1)^b + 1$ . The paper notes the connection between these and perfect polynomials.
- Exponential Equations: The proofs rely heavily on solving equations of the form $x^A(x+1)^B + x^C(x+1)^D = x^E(x+1)^F$ .
Key Lemmas:
- Lemma 5: Relates to the irreducibility of geometric series sums $1 + P + \dots + P^{2n} = Q^m$ .
- Lemma 6: Solves the equation $(x+1)^A + x^B = x^C$ , showing solutions only exist when exponents are powers of 2.
- Lemma 9 (Crucial): Analyzes the equation $x^A(x+1)^B + x^C(x+1)^D = x^E(x+1)^F$ . It proves that if $A \le C \le E$ , then specific constraints on the exponents must hold (specifically, the minimum exponent of $(x+1)$ must be unique and related to the others by powers of 2). This lemma demonstrates that the set of splitting polynomials is not a Sidon set (pairwise sums are not distinct).
Computational Verification:
- The author uses GP-PARI to verify cases where $m=5$ . The proof for $m=5$ involves checking 64 possible configurations of exponent relationships derived from the $m=4$ cases, showing that all lead to contradictions.

3. Key Contributions and Results

Theorem 1: The Case $m=3$

The paper characterizes all sets of three distinct polynomials $\{a, b, c\}$ where all pairwise sums split.

Result: If $a+b, a+c, b+c$ split, then (up to swapping $x$ and $x+1$ ), the polynomials can be expressed as:
$b = a + x^{a_1}(x+1)^{b_2+2s}$
$c = a + x^{a_1+2s}(x+1)^{b_2}$
for some non-negative integer $s$ .
Significance: This provides a complete structural description of 3-element sets satisfying the condition, showing they are generated by specific shifts in the exponents of the splitting forms.

Theorem 2: The Cases $m=4$ and $m>4$

This is the central result of the paper.

Part (i) ( $m=4$ ): The paper classifies all sets of four distinct polynomials $\{a, b, c, d\}$ ${a, b, c, d}$ where all six pairwise sums split. It proves that such sets exist but are highly constrained. They fall into exactly two structural forms (up to symmetry):
1. Form A: Based on powers of $(x+1)$ and a specific polynomial $T(1,3)$ .
2. Form B: Based on polynomials of the form $x^{2t_1} + 1$ and $x^{2t_1} + x^{2t_1-1}$ .
- Note: The proof involves analyzing 16 possible cases of exponent relationships; only two are valid, while 14 are proven impossible via algebraic contradictions (e.g., $v = v-1$ ).
Part (ii) ( $m > 4$ ): The paper proves that no set of 5 or more distinct binary polynomials exists such that all pairwise sums split over $\mathbb{F}_2$ $F_{2}$ .
- Proof Strategy: The author reduces the problem for $m=5$ to checking the consistency of the $m=4$ structures. A computational check confirms that all 64 potential configurations for $m=5$ contain at least one sub-case that is impossible (based on the contradictions found in the $m=4$ analysis).

4. Significance

Resolution of a Polynomial Analogue: The paper successfully resolves the polynomial version of the "sums of powers of 2" problem. It confirms that the threshold for non-existence is $m=5$ , mirroring the integer case where $m=4$ is the limit for all sums being powers of 2 (though the integer case allows $m=3$ , the polynomial case allows specific structures for $m=4$ ).
Structural Insight: The work reveals that the set of "splitting polynomials" (analogous to powers of 2) behaves very differently from the set of integers regarding additive properties. While integers have no Sidon sets of size 4 for powers of 2, the polynomial ring allows specific, highly structured sets of size 4, but strictly forbids size 5.
Methodological Value: The paper demonstrates how elementary algebraic tools (divisor sums, exponent analysis) combined with targeted computer verification can solve problems that are intractable by pure computation alone due to the infinite nature of polynomial rings.
Connection to Perfect Polynomials: By defining Mersenne polynomials and linking them to the divisor sum function $\sigma$ , the paper bridges the gap between additive problems (sums of pairs) and multiplicative properties (divisors) in $\mathbb{F}_2[x]$ .

Conclusion

Luis H. Gallardo proves that $m=5$ is the minimal number such that no set of $m$ distinct binary polynomials exists where all pairwise sums are of the form $x^k(x+1)^\ell$ . The paper provides a complete classification for $m=3$ and $m=4$ , identifying the specific algebraic structures required for such sets to exist, and uses a combination of rigorous algebraic proofs and computational verification to rule out $m \ge 5$ .