# Comparing two definitions of a set of natural numbers

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


• There is no quantifier on your variables, so your meaning is not quite clear to me. It is especially confusing for $N$ since that is not mentioned in the definitions before the colon. Is there a "there exists" for $N$ and the other variables? – Rory Daulton Jan 10 '15 at 20:15
• @RoryDaulton many thanks for your reply. I added more details, hope it is clear now? – user80225 Jan 10 '15 at 20:52
• Yes, much more clear, thanks. – Rory Daulton Jan 10 '15 at 22:16

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.

• many thanks for your answer. It is not clear to me What you mean by $S_i,n_{1i},...$ exactly? Bests – user80225 Jan 17 '15 at 19:57
• @user31009 $S=\prod p_i^{S_i}=p_1^{S_1} p_2^{S_2}\cdots$, $n_1=\prod p_i^{n_{1i}}$, etc. – Alex Ravsky Jan 17 '15 at 20:29
• many thanks again for your reply. In fact, I still do not understand the proof. I see that you take element satisfying $\Delta$ and show that this element satisfying $\Gamma$ and vice versa? To show that they are concide, we need to send each pair (a,b) form the first to a unique pair (x,d) form the second (bijection). So, the question now: is your choice of these pair is unique? thanks again – user80225 Jan 18 '15 at 7:24
• @user31009 I think that to search a bijection between the pairs is a wrong way. Fortunately, we have to prove not the existence of the bijection, but a coincidence of admissible by $\Delta$ products $ab$ and admissible by $\Gamma$ products $xd^2$. Then, using the decomposition of related numbers products into powers of primes, we can deal with powers of each prime independently from the others. This allows us to reduce the initial multiplicative problem to a family of independent additive problems for powers of each prime factor. – Alex Ravsky Jan 18 '15 at 7:56