2
$\begingroup$

I am trying to write a code in Python to do the following. We can express the Erdős-Straus-conjecture in function of some polynomials $x(k), y(k), z(k) \in \mathbb{Q}[k]$ such that $\frac4k = \frac{1}{x(k)} + \frac{1}{y(k)} + \frac{1}{z(k)}$. Notice that the coefficients are rational numbers, but they have to be integers to be able to use them for this conjecture. Following formulas are given:

  1. $ \frac4k = \frac1{uk} + \frac1{vk} + \frac{4uv - u - v}{uvk} \quad(P1)$
  2. $ \frac4k = \frac1{uk} + \frac{4u-1}{uk+v} + \frac{(4u-1)v}{uk(uk+v)}\quad (P2) $
  3. $ \frac4k = \frac{4u}{uk+v+1} + \frac4{k(uk+v+1)} + \frac{4v}{k(uk+v+1)}\quad (P3)$
  4. $ \frac4k = \frac4{k+v} + \frac{4v}{k(k+4u+v)} + \frac{16uv}{k(k+v)(k+4u+v)} \quad (P4) $

The following theorem is used to determine when polynomials yield integer values: Consider $f \in \mathbb{Q}[k]$ en choose $m \in \mathbb{Z}$ such that $m \cdot f$ only has integer coefficients. Now consider $n = am+b \in \mathbb{Z}$ with $0 \le b < m$. Then $f(n) \in \mathbb{Z}$ iff $(m\cdot f)(b) \equiv 0\,\,(mod\,\,m)$.

This theorem implies that only looking at the residue classes modulo $m$ is sufficient to find out for which integers $n$ also $f(n)$ will be an integer.

For the Erdös-Straus-conjucture I have three polynomials $f_1(n), f_2(n), f_3(n)$. I want to find out for which $n$ all three polynomials have integer coefficients. Consider the corresponding $m$-values $m_1,m_2,m_3$ and let $m$ be equal to $lcm(m_1,m_2,m_3)$. Applying the above theorem (with the $m$ found), it's enough to check for which residue classes modulo $m$ all three polynomials $f_1,f_2,f_3$ will be integers.

So, I'd like to write a function in Python that has concrete values of $u$ and $v$ as input. I want to calculate the correct value for $m$ and to check for which residue classes modulo $m$ the polynomials have integer values. Therefore, the output should be a tuple ($m$,L) with L the list of residue classes modulo $m$ (that satisfy the conditions). I want to be able to use this function for (P1), (P2), (P3) and (P4).

This is what I've got so far:

P.<k> = PolynomialRing(QQ)
var('x,y,z')
def P1(u,v):
    x = u*k
    y = v*k
    z = (u*v*k)/(4*u*v-u-v)
    return (x,y,z)
def P2(u,v):
    x = u*k
    y = (u*k+v)/(4*u-1)
    z = (u*k*(u*k+v))/((4*u-1)*v)
    return (x,y,z)
def P3(u,v):
    x = (u*k+v+1)/(4*u)
    y = (k*(u*k+v+1))/4
    z = (k*(u*k+v+1))/(4*v)
    return (x,y,z)
def P4(u,v):
    x = (k+v)/4
    y = (k*(k+4*u+v))/(4*v)
    z = (k*(k+v)*(k+4*u+v))/(16*u*v)
    return (x,y,z)

var('m,k')
def findM(f):
    m = (f(k=1)^-1).denominator() 
    return m  
var('u,v,P,m1,m2,m3,m,k')
def mP(u,v,P):
    D = P(u,v)
    m1 = findM(D[0])
    m2 = findM(D[1])
    m3 = findM(D[2])
    m = lcm([m1,m2,m3])
    L = []
    for i in xrange(1,m-1):
         if((D[0](k=i)^-1).denominator() == 1 and (D[1](k=i)^-1).denominator() == 1 and (D[2](k=i)^-1).denominator() == 1 and Mod(m*((D[0]^-1) + (D[1]^-1) + (D[2]^-1))(k=b),m) == 0):
             L.append(i)
    return (m,L)

The problem is a keep getting an empty list. I'm using Sage Math to compute this (which is based on Python - kinda). Can someone please help me.

Infinitely grateful!

$\endgroup$
1
$\begingroup$

The following is a possible implementation, which you can test here.


R. = PolynomialRing(QQ)
D. = PolynomialRing(ZZ)
def P1(u,v):
    x = u*k
    y = v*k
    z = (u*v*k)/(4*u*v-u-v)
    return (x,y,z)
def P2(u,v):
    x = u*k
    y = (u*k+v)/(4*u-1)
    z = (u*k*(u*k+v))/((4*u-1)*v)
    return (x,y,z)
def P3(u,v):
    x = (u*k+v+1)/(4*u)
    y = (k*(u*k+v+1))/4
    z = (k*(u*k+v+1))/(4*v)
    return (x,y,z)
def P4(u,v):
    x = (k+v)/4
    y = (k*(k+4*u+v))/(4*v)
    z = (k*(k+v)*(k+4*u+v))/(16*u*v)
    return (x,y,z)
def findM(f):
    m = f.denominator() 
    return m
def mP(u,v,P):
    f = P(u,v)
    m1 = findM(f[0])
    m2 = findM(f[1])
    m3 = findM(f[2])
    m = lcm([m1,m2,m3])
    F = [D(m*f[0]),D(m*f[1]),D(m*f[2])]
    L = []
    for i in xrange(1,m+1):
         if(Mod(F[0](i),m)==0 and Mod(F[1](i),m)==0 and Mod(F[2](i),m)==0):
             L.append(i)
    return (m,L)
#Example:
[u,v,P] = [3/5,5,P4]
[m,S] = mP(u,v,P)
[x,y,z] = P(u,v)

print("[u,v,m] = ",[u,v,m])
print("[k,x(k),y(k),z(k),check]:")
for k in S:
    [xk,yk,zk] = [x(k),y(k),z(k)]
    chk = 1/xk + 1/yk + 1/zk
    print [k,xk,yk,zk,chk==4/k]

The example, using $(u,v)=(3/5,5)$ and $P4$, will return


[75, 20, 309, 10300, True]
[175, 45, 1596, 119700, True]
[375, 95, 7170, 1135250, True]
[475, 120, 11457, 2291400, True]
[675, 170, 23031, 6525450, True]
[775, 195, 30318, 9853350, True]
[975, 245, 47892, 19555900, True]
[1075, 270, 58179, 26180550, True]

The first line would mean $$ \frac{4}{75} = \frac{1}{20} + \frac{1}{309} + \frac{1}{10300} $$


You declared


P.<k> = PolynomialRing(QQ)

but later this removes the declaration:


var('u,v,P,m1,m2,m3,m,k')

You might want to assign a universal ring $R:=\mathbb Q[k]$ that is untouched throughout instead. Might also be a good idea to have an integral ring $D:=\mathbb Z[k]$ since you will work in it later, but I guess it's not necessary. i.e.


R.<k> = PolynomialRing(QQ)  
D.<k> = PolynomialRing(ZZ)

For finding $m$, it suffices to use


def findM(f):
    m = f.denominator() 
    return m  

The current command


(f(k=1)^-1).denominator()

will find the numerator instead, and evaluated at $f(1)$ so not the true denominator.

One last point is xrange(1,m-1) gives you the range $[1,2,\dots,m-2]$ but you want $[1,2,\dots,m]$.

$\endgroup$
  • $\begingroup$ Thank you so much! It works and I understand what you wrote. $\endgroup$ – Zachary Dec 10 '18 at 10:22
  • $\begingroup$ @Zachary Glad to have helped! $\endgroup$ – Yong Hao Ng Dec 10 '18 at 10:45

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.