# Explaining $Z(X)f(X) = g(X)Z(\omega X)$

is a clever trick used in polynomial-based set equality checks. Let’s break it down step by step with an example.

Here is what we've got;

1. Polynomials $f(X)$ and $g(X)$ :
These interpolate values from the sets $A = \{a_0, a_1, \ldots, a_{k-1}\}$ and $B = \{b_0, b_1, \ldots, b_{k-1}\}$ , respectively. For example:
$f(X) = (a_0 + X)(a_1 + X)\cdots(a_{k-1} + X)$,
$g(X) = (b_0 + X)(b_1 + X)\cdots(b_{k-1} + X)$.

2. Roots of Unity $\omega$ :
The domain $H = \{1, \omega, \omega^2, \ldots, \omega^{k-1}\}$ is built from a primitive $k -th$ root of unity $\omega$ , such that $\omega^k = 1$ . For example:
• If $k = 4$, then $\omega$ might be a complex number like $i = \sqrt{-1}$ (since $i^4 = 1$).
• $H = \{1, i, -1, -i\}$.

3. Polynomial $Z(X)$:
This is a “helper polynomial” that relates $f(X)$ and $g(X)$ . Its purpose is to adjust $f(X)$ and $g(X)$ at points in $H$ to test for set equality.

**Approach**
If $A$ and $B$ are equal, then $f(X) = g(X)$ , and $Z(X)$ simplifies to $Z(X) = 1$ . Otherwise, $Z(X)$ acts as a transformation that “balances” $f(X)$ and $g(X)$ over the domain $H$.

**Example: Checking Two Sets**

Step 1: Define Sets

Let’s check if $A = \{1, 2, 3\}$ and $B = \{3, 2, 1\}$ are equal.

Step 2: Construct Polynomials

1. For $A$ , construct:

$f(X) = (1 + X)(2 + X)(3 + X)$.

2. For $B$ , construct:

$g(X) = (3 + X)(2 + X)(1 + X)$.

Notice that $f(X) = g(X)$ since the sets $A$ and $B$ contain the same elements.

Step 3: Choose a Root of Unity Domain

Let $k = 3$ , and let $\omega$ be a primitive 3rd root of unity such that $\omega^3 = 1$ (e.g., $\omega = e^{2\pi i / 3}$ ).

Then the domain $H = \{1, \omega, \omega^2\}$ .

Step 4: Define $Z(X)$

For this example:
• If $f(X) = g(X) , Z(X) = 1$ satisfies:

$Z(X)f(X) = g(X)Z(\omega X)$.

**Case: Unequal Sets**

Now let’s take $A = \{1, 2, 3\}$ and $B = \{4, 5, 6\}$ .
1. Construct $f(X)$ and $g(X)$:

$f(X) = (1 + X)(2 + X)(3 + X)$,

$g(X) = (4 + X)(5 + X)(6 + X)$.

2. Check at $X = 1$:
Evaluate $f(1)$ and $g(1)$:

$f(1) = (1 + 1)(2 + 1)(3 + 1) = 2 \cdot 3 \cdot 4 = 24$,

$g(1) = (4 + 1)(5 + 1)(6 + 1) = 5 \cdot 6 \cdot 7 = 210$.

Clearly, $f(1) \neq g(1)$, so the sets $A$ and $B$ are not equal.

If $f(X) \neq g(X)$, no $Z(X)$ can balance them over $H$ , proving $A \neq B$.