Comparing two definitions of a set of natural numbers

Question

Let $n_1,n_2,N\in \mathbb{N}$. I want to show the following:

The two sets \begin{align*} &\Delta(n_1,n_2,N)\\ =& \Big\{ a\cdot b: \quad a\mid {n_1}^2,~a^2 \mid {n_1}^2N ,\gcd\left(N ,a\right)\text { is a perfect square},~b\mid {n_2}^2 ,b^2\mid \frac{{n_1}^2{n_2}^2 }{a^2}N , \text{ and }\gcd\big(\frac{{n_1}^2}{a^2}N ,b\big)\text { is a perfect square} \Big\} \end{align*} and \begin{align*} &\Gamma(n_1,n_2,N)\\ =&\Big\{ x\cdot d^2:\quad d\mid \gcd(n_1,n_2),~ x\mid \frac{{n_1}^2{n_2}^2 }{d^4}, x^2\mid \frac{{n_1}^2{n_2}^2 }{d^4} N , \text{ and } \gcd\left(N ,x\right)\text { is a perfect square} \Big\} \end{align*}

are equal (as sets), i.e, $\Delta(n_1,n_2,N)=\Gamma(n_1,n_2,N)$.

I checked it numerically and it is true. So I am interested in the mathematical explanation for this (for computational reasons). It is not clear to me at all what kind of substitutions should I consider to show this.

Numerical evidence

def group1(n1,n2,N):
    mylist=[]
    for a in divisors(n1^2):
        if is_square(gcd(N,a)):
            f=sqrt(gcd(N,a))
            if a^2 in divisors(n1^2*N):
                for b in divisors(n2^2):
                    if b^2 in divisors(n1^2*n2^2*N/a^2):
                       if is_square(gcd(b,N*n1^2/a^2)): 
                           mylist.append((a*b))
    mylist.sort()
    return mylist      

def group2(n1,n2,N):
    mylist=[]
    for d in divisors(gcd(n1,n2)):
        for x in divisors(n1^2*n2^2/d^4):
            if x^2 in divisors(n1^2*n2^2*N/d^4):
              if is_square(gcd(N,x)):
                   mylist.append( (x*d^2))
    mylist.sort()
    return mylist     

The result:

for (n1,n2,N) in list(mrange([100,100,100])):
    if n1*n2*N!=0:
        group1(n1,n2,N)==group2(n1,n2,N)
output:
True
True
True
True
True
True
True
True
True
True
True
True
....
....

Any answer? Thanks.

Answer 1

It seems the following.

It is weird how without a proof one can come to an idea that so complexly determined sets coincide. Moreover, my proof of the coincidence is complex too. Let’s begin.

I have to remark that all introduced numbers will be non-negative integers.

At the first we transform a multiplicative problem into additive. Let $\{p_i\}$ be an enumeration of prime numbers. For each index $i$ and each number $t$ used in the formulation of the question let $t=p_1^{t_1}p_2^{t_2}\dots$ be a prime decomposition of the number $t$. Fix the numbers $n_1$, $n_2$, and $N$.

Then $S\in\Delta(n_1,n_2,N)$ iff for each index $i$ there exist numbers satisfying the following conditions $\Delta_i$:

$$S_i=a_i+b_i,$$

$$a_i\le 2n_{1i},$$

$$2a_i\le 2n_{1i}+N_i,$$

$$\min(a_i,N_i)\mbox{ is even},$$

$$b_i\le 2n_{2i},$$

$$2b_i\le 2n_{1i}+2n_{2i}+N_i-2a_i,$$

$$\min(2n_{1i}+N_i-2a_i,b_i)\mbox{ is even}.$$

Then $t\in\Gamma(n_1,n_2,N)$ iff for each index $i$ there exist numbers satisfying the following conditions $\Gamma_i$:

$$S_i=x_i+2d_i,$$

$$d_i\le\min(n_{1i},n_{2i}),$$

$$x_i\le 2n_{1i}+2n_{2i}-4d_i,$$

$$2x_i\le 2n_{1i}+2n_{2i}+N_i-4d_i,$$

$$\min(x_i,N_i)\mbox{ is even}.$$

So it suffices to show that for each index $i$ the ranges for $S_i$ defined by these conditions coincide.

Fix an index $i$. For the simplicity we will drop the index $i$ in the following. Put $$M=\min (2n_1+2n_2, n_1+n_2+N/2).$$ If $S$ satisfies either of conditions $\Delta$ or $\Gamma$, then $S\le M$. So, imposing the restriction $S\le M$, we can simplify condition $\Delta$:

$$S=a+b,$$

$$a\le 2n_1,$$

$$2a\le 2n_1+N,$$

$$\min(a,N)\mbox{ is even},$$

$$b\le 2n_2,$$

$$\min(2n_1+N-2a,b)\mbox{ is even}.$$

and $\Gamma$:

$$S=x+2d,$$

$$d\le\min(n_1,n_2),$$

$$x\le 2n_1+2n_2-4d,$$

$$\min(x,N)\mbox{ is even}.$$

Now there are four possible cases.

1 $S$ is even, $N$ is even. Then $S\in\Gamma$. To show this it suffice to put $d=0$ and $$x=S\le M=2n_1+2n_2-4d.$$ To show that $S\in\Delta$ put $b=\min(2n_2, S)\le M$, $a=S-b$. If $b=S$ then $$a=0\le\min(2n_1,n_1+N/2),$$ if $b=2n_2$ then $$a\le M-2n_2\le \min(2n_1,n_1-n_2+N/2)\le \min(2n_1,n_1+N/2).$$ Since $S$ and $b$ are even then $a=S-b$ is even. Since $N$ is even, $\min(a,N)$ is even and $\min(2n_1+N-2a,b)$ is even.

2 $S$ is even, $N$ is odd. Let $K=\min(n_1,n_2)$. If $S\in\Gamma$ then $x$ is even and $x<N$, so $$S=x+2d<N+2K.$$ Conversely, suppose that $S<N+2K$. If $S\le 2K$ put $d=S/2$ and $$x=0\le 2n_1+2n_2-4K\le 2n_1+2n_2-2S= 2n_1+2n_2-4d.$$ Then $\min(x,N)=x=0$ is even. If $S>2K$ then put $x=\min(N-1,S)$ and $2d=S-x$. Then $\min(x,N)=x$ is even. If $x=S$ then $d=0\le K$ and $$S\le M\le 2n_1+2n_2=2n_1+2n_2-4d.$$ If $x=N-1$ then $$2d=S-x<N+2K-N+1=2K+1,$$ so $d\le K$. Moreover, $$x+4d=x+2(S-x)=2S-x\le 2M-N+1\le 2n_1+2n_2+N-N+1.$$ Since $x$ is even, $x\le 2n_1+2n_2-4d$.

If $S\in\Delta$ then $b$ is even, $b<2n_1+N-2a$, $a$ is even and $a<N$. Therefore $$S=a+b<2n_1+N-a<N+2n_1$$ and $S<N+b\le N+2n_2$. So, $$S<N+2\min(n_1,n_2)=N+2K.$$ Conversely, if $S<N+2K$ then put $b=\min(S,2n_2)\le 2n_2$ and $a=S-b$. If $b=S$ then $$a=0\le\min (2n_1, n_1+N/2),$$ $\min(a,N)=0$ is even and $$\min(2n_1+N-2a,b)=\min(2n_1+N,S)=S$$ is even, because $$S<N+2K\le N+2n_1.$$ If $b=2n_2$ then $$a=S-2n_2\le M-2n_2=$$ $$\min (2n_1+2n_2, n_1+n_2+N/2)-2n_2=$$ $$\min(2n_1, n_1-n_2+N/2)\le$$ $$\min (2n_1, n_1+N/2),$$ $$\min(2n_1+N-2a,b)=$$ $$\min(2n_1+N-2(S-2n_2),2n_2)=$$ $$\min(2n_1+4n_2+N-2S,2n_2)=2n_2$$ is even, because $$2n_1+4n_2+N-2S-2n_2=$$ $$2n_1+2n_2+N-2S\ge$$ $$2n_1+2n_2+N-2M=$$ $$2n_1+2n_2+N-2\min (2n_1+2n_2, n_1+n_2+N/2)\ge 0,$$ and $$\min(a,N)=\min (S-2n_2,N)=S-2n_2$$ is even, because $$S-2n_2<N+2K-2n_2\le N.$$

3 $S$ is odd, $N$ is even. If $S\in\Gamma$ then $x$ is odd. Hence $x>N$, so $S=x+2d>N$. Conversely, if $S>N$ then put $x=S$, $d=0$. Then $$x\le M\le 2n_1+2n_2=2n_1+2n_2-4d$$ and $\min(x,N)=N$ is even. If $S\in\Delta$ and $S<N$ then $\min(a,N)=a$ and $a$ is even. Then $b=S-a$ is odd and $$\min(2n_1+N-2a,b)=2n_1+N-2a.$$ So $2n_1+N-2a<b$. Then $$N\le 2n_1+N-2a<b\le a+b=S<N,$$ a contradiction. Let $S>N$. We are going show that $S\in\Delta$. Let $K=\min (2n_1,n_1+N/2, S)$. There are two possible cases.

3.1 $K$ is odd and $K<N$. Then $K<S$, so $$K=n_1+N/2<M\le n_1+n_2+N/2$$ and $n_2>0$. Put $a=K-1$. Then $\min(a,N)$ is even. Put $b=S-a=S-K+1\ge 2$. Then $$b\le M-(n_1+N/2)+1\le n_2+1\le 2n_2$$ and $$\min(2n_1+N-2a,b)=\min(2,b)=2$$ is even.

3.2 Not 3.1. Put $a=K$. Then $\min(a,N)$ is even. Put $b=S-a$. If $a=S$ then $$b=0\le 2n_2$$ and $$\min(2n_1+N-2a,b)=\min(N-2n_1,0)=0$$ is even, if $a=2n_1$ then $$b\le M-2n_1\le 2n_2$$ and $$\min(2n_1+N-2a,b)=\min(N-2n_1,S-2n_1)= N-2n_1$$ is even, if $a=n_1+N/2$ then $$b\le M-(n_1+N/2)\le n_2$$ and $$\min(2n_1+N-2a,b)=\min(0,b)$$ is even.

4 $S$ is odd, $N$ is odd. Both of the cases $S\in\Delta$ and $S\in\Gamma$ are impossible. Indeed, if $S\in\Delta$ then $\min(2n_1+N-2a,b)$ is even, so $b$ is even, and $\min(a,N)$ is even, so $a$ is even. Then $S=a+b$ is even, a contradiction. If $ S\in\Gamma$ then $x$ is odd, so $\min(x,N)$ is odd, a contradiction.