Comparación de dos definiciones de un conjunto de números naturales

Question

Dejemos que $n_1,n_2,N\in \mathbb{N}$ . Quiero mostrar lo siguiente:

Los dos conjuntos \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*} y \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*}

son iguales (como conjuntos), es decir $\Delta(n_1,n_2,N)=\Gamma(n_1,n_2,N)$ .

Lo he comprobado numéricamente y es cierto. Así que me interesa la explicación matemática de esto (por razones computacionales). No me queda nada claro qué tipo de sustituciones debo considerar para demostrarlo.

Pruebas numéricas

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     

El resultado:

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

¿Alguna respuesta? Gracias.

Answer 1

Parece lo siguiente.

Es extraño que sin una prueba se pueda llegar a la idea de que coinciden conjuntos tan complejamente determinados. Además, mi prueba de la coincidencia también es compleja. Empecemos.

Tengo que señalar que todos los números introducidos serán enteros no negativos.

En el primero transformamos un problema multiplicativo en aditivo. Sea $\{p_i\}$ sea una enumeración de números primos. Para cada índice $i$ y cada número $t$ utilizado en la formulación de la pregunta deja $t=p_1^{t_1}p_2^{t_2}\dots$ sea una descomposición prima del número $t$ . Fijar los números $n_1$ , $n_2$ y $N$ .

Entonces $S\in\Delta(n_1,n_2,N)$ si para cada índice $i$ existen números que satisfacen las siguientes condiciones $\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}.$$

Entonces $t\in\Gamma(n_1,n_2,N)$ si para cada índice $i$ existen números que satisfacen las siguientes condiciones $\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}.$$

Por tanto, basta con demostrar que para cada índice $i$ los rangos para $S_i$ definidos por estas condiciones coinciden.

Fijar un índice $i$ . Para simplificar, dejaremos de lado el índice $i$ en lo siguiente. Poner $$M=\min (2n_1+2n_2, n_1+n_2+N/2).$$ Si $S$ cumple cualquiera de las condiciones $\Delta$ o $\Gamma$ entonces $S\le M$ . Por lo tanto, la imposición de la restricción $S\le M$ podemos simplificar la condición $\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}.$$

y $\Gamma$ :

$$S=x+2d,$$

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

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

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

Ahora hay cuatro casos posibles.

1 $S$ está en paz, $N$ está en paz. Entonces $S\in\Gamma$ . Para demostrarlo basta con poner $d=0$ y $$x=S\le M=2n_1+2n_2-4d.$$ Para demostrar que $S\in\Delta$ poner $b=\min(2n_2, S)\le M$ , $a=S-b$ . Si $b=S$ entonces $$a=0\le\min(2n_1,n_1+N/2),$$ si $b=2n_2$ entonces $$a\le M-2n_2\le \min(2n_1,n_1-n_2+N/2)\le \min(2n_1,n_1+N/2).$$ Desde $S$ y $b$ son incluso entonces $a=S-b$ está en paz. Como $N$ está en paz, $\min(a,N)$ es par y $\min(2n_1+N-2a,b)$ está en paz.

2 $S$ está en paz, $N$ es impar. Dejemos que $K=\min(n_1,n_2)$ . Si $S\in\Gamma$ entonces $x$ es par y $x<N$ Así que $$S=x+2d<N+2K.$$ A la inversa, supongamos que $S<N+2K$ . Si $S\le 2K$ poner $d=S/2$ y $$x=0\le 2n_1+2n_2-4K\le 2n_1+2n_2-2S= 2n_1+2n_2-4d.$$ Entonces $\min(x,N)=x=0$ es uniforme. Si $S>2K$ entonces pon $x=\min(N-1,S)$ y $2d=S-x$ . Entonces $\min(x,N)=x$ es par. Si $x=S$ entonces $d=0\le K$ y $$S\le M\le 2n_1+2n_2=2n_1+2n_2-4d.$$ Si $x=N-1$ entonces $$2d=S-x<N+2K-N+1=2K+1,$$ así que $d\le K$ . Además, $$x+4d=x+2(S-x)=2S-x\le 2M-N+1\le 2n_1+2n_2+N-N+1.$$ Desde $x$ está en paz, $x\le 2n_1+2n_2-4d$ .

Si $S\in\Delta$ entonces $b$ está en paz, $b<2n_1+N-2a$ , $a$ es par y $a<N$ . Por lo tanto, $$S=a+b<2n_1+N-a<N+2n_1$$ y $S<N+b\le N+2n_2$ . Así que, $$S<N+2\min(n_1,n_2)=N+2K.$$ Por el contrario, si $S<N+2K$ entonces pon $b=\min(S,2n_2)\le 2n_2$ y $a=S-b$ . Si $b=S$ entonces $$a=0\le\min (2n_1, n_1+N/2),$$ $\min(a,N)=0$ es par y $$\min(2n_1+N-2a,b)=\min(2n_1+N,S)=S$$ es par, porque $$S<N+2K\le N+2n_1.$$ Si $b=2n_2$ entonces $$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$$ es par, porque $$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,$$ y $$\min(a,N)=\min (S-2n_2,N)=S-2n_2$$ es par, porque $$S-2n_2<N+2K-2n_2\le N.$$

3 $S$ es impar, $N$ está en paz. Si $S\in\Gamma$ entonces $x$ es impar. Por lo tanto, $x>N$ Así que $S=x+2d>N$ . Por el contrario, si $S>N$ entonces pon $x=S$ , $d=0$ . Entonces $$x\le M\le 2n_1+2n_2=2n_1+2n_2-4d$$ y $\min(x,N)=N$ es par. Si $S\in\Delta$ y $S<N$ entonces $\min(a,N)=a$ y $a$ es par. Entonces $b=S-a$ es impar y $$\min(2n_1+N-2a,b)=2n_1+N-2a.$$ Así que $2n_1+N-2a<b$ . Entonces $$N\le 2n_1+N-2a<b\le a+b=S<N,$$ una contradicción. Sea $S>N$ . Vamos a demostrar que $S\in\Delta$ . Sea $K=\min (2n_1,n_1+N/2, S)$ . Hay dos casos posibles.

3.1 $K$ es impar y $K<N$ . Entonces $K<S$ Así que $$K=n_1+N/2<M\le n_1+n_2+N/2$$ y $n_2>0$ . Poner $a=K-1$ . Entonces $\min(a,N)$ está en paz. Poner $b=S-a=S-K+1\ge 2$ . Entonces $$b\le M-(n_1+N/2)+1\le n_2+1\le 2n_2$$ y $$\min(2n_1+N-2a,b)=\min(2,b)=2$$ está en paz.

3.2 No 3.1. Poner $a=K$ . Entonces $\min(a,N)$ está en paz. Poner $b=S-a$ . Si $a=S$ entonces $$b=0\le 2n_2$$ y $$\min(2n_1+N-2a,b)=\min(N-2n_1,0)=0$$ es par, si $a=2n_1$ entonces $$b\le M-2n_1\le 2n_2$$ y $$\min(2n_1+N-2a,b)=\min(N-2n_1,S-2n_1)= N-2n_1$$ es par, si $a=n_1+N/2$ entonces $$b\le M-(n_1+N/2)\le n_2$$ y $$\min(2n_1+N-2a,b)=\min(0,b)$$ está en paz.

4 $S$ es impar, $N$ es impar. Ambos casos $S\in\Delta$ y $S\in\Gamma$ son imposibles. De hecho, si $S\in\Delta$ entonces $\min(2n_1+N-2a,b)$ es par, por lo que $b$ es par, y $\min(a,N)$ es par, por lo que $a$ está en paz. Entonces $S=a+b$ es uniforme, una contradicción. Si $ S\in\Gamma$ entonces $x$ es impar, así que $\min(x,N)$ es impar, una contradicción.