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,\dots ,a_{k-1}\}$ and
   $B=\{b_0,b_1,\dots ,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,\dots ,{\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)\ne g(1)$, so the sets

$A$ and

$B$ are not equal.

If

$f(X)\ne g(X)$, no

$Z(X)$ can balance them over

$H$ , proving

$A\ne B$.