Inductively computing Mersenne primes / perfect numbers?

Question

For two sets $A,B$ set $A+B = \{a +b | a \in A,b \in B\}$. Let $(x_n)_{n \in \mathbb{N}}$ be independent variables. Let $\sigma(n)$ be the sum of divisors of $n$.

Set $\hat{\phi}(1) = \{x_1\}$ and then inductively:

$$\hat{\phi}(n) = \{x_n\}$$

if $\sigma(k) \neq n$ for all $k \in \mathbb{N}$ and $$\hat{\phi}(n) = \bigcup_{ \sigma(m) = n} \left\{ \sum_{d|m} \hat{\phi}(d) \right\}$$ otherwise.

Examples:

1 [x1]
2 [x2]
3 [x1 + x2]
4 [2*x1 + x2]
5 [x5]
6 [x1 + x5]
7 [3*x1 + 2*x2]
8 [4*x1 + 2*x2]
9 [x9]
10 [x10]
11 [x11]
12 [x1 + x11, 3*x1 + 2*x2 + x5]
13 [2*x1 + x2 + x9]
14 [3*x1 + x2 + x9]
15 [7*x1 + 4*x2]
16 [x16]
17 [x17]
18 [x1 + x10 + x2 + x5, x1 + x17]
19 [x19]
20 [x1 + x19]
21 [x21]
22 [x22]
23 [x23]
24 [9*x1 + 5*x2 + x5, x1 + x23, 7*x1 + 4*x2 + x9]
25 [x25]
26 [x26]
27 [x27]
28 [8*x1 + 5*x2 + 2*x5, 6*x1 + x11 + 3*x2 + x5]

Conjecture: Let $n=2^{p-1}(2^p-1)$ be an even perfect number. Then there exists a $x \in \hat{\phi}(2n)$, such that, if we plug in $1$ for all free variables in $x$ we get:

$$ y = x(1,\cdots,1)$$ such that: $$ y+1 = 2^q-1$$ is a Mersenne prime. Furthermore we have: $$N=2^{q-1}(2^q-1)$$ is the next even perfect number after $n$.

I have tested this for $n=6,28,496$. Unfortunately, my naive computation method hits the limit for the next perfect number. So I am asking if somebody can check if the next perfect number satisfies this conjecture or not?

It would be nice if you share also your method to check the number.

Thanks for your help!

Here is some SAGE code I used.

And here is some output:

n y
6 2
6 6
28 30
496 2
496 126

Edit: Here are the trees corresponding to $2\cdot 6$:

[ (                                                                    )                                ]
[ ( (12, 6, 1), (12, 6, 2),   ____(12, 6, 3)        ____(12, 6, 6)     )                                ]
[ (                          /         /           /         /         )  (                           ) ]
[ (                         (3, 2, 1) (3, 2, 2) , (6, 5, 1) (6, 5, 5)  ), ( (12, 11, 1), (12, 11, 11) ) ]

And here are the corresponding trees to $2\cdot 28$:

[ (                                                                                                                                                                            
[ ( (56, 28, 1), (56, 28, 2),   _______(56, 28, 4)               _____________(56, 28, 7)_____                         _____________(56, 28, 14)____                           
[ (                            /               /                /         /                  /                        /                            /                           
[ (                           (4, 3, 1)   ____(4, 3, 3)        (7, 4, 1) (7, 4, 2)   _______(7, 4, 4)                (14, 13, 1)   _______________(14, 13, 13)_____            
[ (                                      /         /                                /               /                             /                /              /            
[ (                                     (3, 2, 1) (3, 2, 2)  ,                     (4, 3, 1)   ____(4, 3, 3)                     (13, 9, 1)   ____(13, 9, 3)     (13, 9, 9)    
[ (                                                                                           /         /                                    /         /                       
[ (                                                                                          (3, 2, 1) (3, 2, 2)   ,                        (3, 2, 1) (3, 2, 2)              , 

                                                                                                                                                                    )  (                                                            
  ____________________________________________________________(56, 28, 28)___________________________________________________                                       )  ( (56, 28, 1), (56, 28, 2),   _______(56, 28, 4)             
 /           /                 /                       /                            /                                       /                                       )  (                            /               /               
(28, 12, 1) (28, 12, 2)   ____(28, 12, 3)      _______(28, 12, 4)              ____(28, 12, 6)      _______________________(28, 12, 12)______________               )  (                           (4, 3, 1)   ____(4, 3, 3)        
                         /         /          /               /               /         /          /          /                /                    /               )  (                                      /         /           
                        (3, 2, 1) (3, 2, 2)  (4, 3, 1)   ____(4, 3, 3)       (6, 5, 1) (6, 5, 5)  (12, 6, 1) (12, 6, 2)   ____(12, 6, 3)       ____(12, 6, 6)       )  (                                     (3, 2, 1) (3, 2, 2)  , 
                                                        /         /                                                      /         /          /         /           )  (                                                            
                                                       (3, 2, 1) (3, 2, 2)                                              (3, 2, 1) (3, 2, 2)  (6, 5, 1) (6, 5, 5)    ), (                                                            

                                                                                                                                                                                                                                             )                 
  _____________(56, 28, 7)_____                         _____________(56, 28, 14)____                             ___________________________________________________(56, 28, 28)__________________________________________                  )                 
 /         /                  /                        /                            /                            /           /                 /                       /                            /                     /                  )  (              
(7, 4, 1) (7, 4, 2)   _______(7, 4, 4)                (14, 13, 1)   _______________(14, 13, 13)_____            (28, 12, 1) (28, 12, 2)   ____(28, 12, 3)      _______(28, 12, 4)              ____(28, 12, 6)      _____(28, 12, 12)        )  ( (56, 39, 1), 
                     /               /                             /                /              /                                     /         /          /               /               /         /          /           /             )  (              
                    (4, 3, 1)   ____(4, 3, 3)                     (13, 9, 1)   ____(13, 9, 3)     (13, 9, 9)                            (3, 2, 1) (3, 2, 2)  (4, 3, 1)   ____(4, 3, 3)       (6, 5, 1) (6, 5, 5)  (12, 11, 1) (12, 11, 11)   )  (              
                               /         /                                    /         /                                                                               /         /                                                          )  (              
                              (3, 2, 1) (3, 2, 2)   ,                        (3, 2, 1) (3, 2, 2)              ,                                                        (3, 2, 1) (3, 2, 2)                                                   ), (              

                                                                                                                                                                                                                                            
                                                                                                                                                                                                                                            
                                                                                                                                                                                                    )  (                                    
  ____(56, 39, 3)       _______________(56, 39, 13)_____             _______________________________________________(56, 39, 39)______________________________________                              )  ( (56, 39, 1),   ____(56, 39, 3)     
 /         /           /                /              /            /           /                 /                    /              /                              /                              )  (               /         /          
(3, 2, 1) (3, 2, 2) , (13, 9, 1)   ____(13, 9, 3)     (13, 9, 9)   (39, 18, 1) (39, 18, 2)   ____(39, 18, 3)      ____(39, 18, 6)    (39, 18, 9)   _________________(39, 18, 18)_______             )  (              (3, 2, 1) (3, 2, 2) , 
                                  /         /                                               /         /          /         /                      /           /           /           /             )  (                                    
                                 (3, 2, 1) (3, 2, 2)             ,                         (3, 2, 1) (3, 2, 2)  (6, 5, 1) (6, 5, 5)              (18, 10, 1) (18, 10, 2) (18, 10, 5) (18, 10, 10)   ), (                                    

                                                                                                                                                        ]
                                                                                                                                                        ]
                                                                                                                                                      ) ]
  _______________(56, 39, 13)_____             _________________________________________(56, 39, 39)________________________________                  ) ]
 /                /              /            /           /                 /                    /              /                  /                  ) ]
(13, 9, 1)   ____(13, 9, 3)     (13, 9, 9)   (39, 18, 1) (39, 18, 2)   ____(39, 18, 3)      ____(39, 18, 6)    (39, 18, 9)   _____(39, 18, 18)        ) ]
            /         /                                               /         /          /         /                      /           /             ) ]
           (3, 2, 1) (3, 2, 2)             ,                         (3, 2, 1) (3, 2, 2)  (6, 5, 1) (6, 5, 5)              (18, 17, 1) (18, 17, 17)   ) ]
 

The trees were constructed with the following code:

def inductiveGraph(n):
    from itertools import product
    ll = [i for i in range(1,n) if sigma(i)==n]
    #print(ll)
    if len(ll)==0:
        return [LabelledOrderedTree([],label=n)]
    else:
        phll = []
        for m in ll:
            ml = list(product(*[ [ LabelledOrderedTree(ph,label=(n,m)) for ph in inductiveGraph(d)] for d in divisors(m)]))
            #print(n,ml)
            for x in ml:
                phll.append( x)
        return phll
    
print(ascii_art(inductiveGraph(2*28))) 

Furthermore, plugging in $1$ for all variables in $x(1,\cdots,1)$ counts the number of leafs in the tree which corresponds to $x \in \hat{\phi}(2n)$.

Related question: Additive number theory, Hilbert spaces and polynomial rings?

Answer 1

The conjecture fails for $n=8128$, which can be verified in matter of seconds as explained below. I used PARI/GP for my verification.

First, since the conjecture concerns only values of at $x$'s being all ones, there is no need to compute explicitly $\hat\phi(n)$ but only its evaluation $f_n:=\hat\phi(n)(1,1,\dots,1)$.

Clearly, we have $f_1=\{1\}$ and for $n>1$, $f_n=\{1\}$ if $\sigma^{-1}(n)=\emptyset$, otherwise $$f_n = \bigcup_{m\in\sigma^{-1}(n)} \left(\sum_{d|m} f_d\right).$$

Second, to verify the conjecture for $n=8128$, we need to compute $f_{16256}$ -- let's round the index bound to $20000$. Since we will need to quickly get values for $\sigma^{-1}(x)$ for $x\leq 20000$, it's better to get them precomputed in vector is (although for larger values one also can use my invsigma() routine):

is = vector(20000,i,[]); for(i=1,#is, s=sigma(i); if(s<=#is,is[s]=concat(is[s],[i])) );

Third, we will need function sumset(S) that computes the sum of sets given as elements of the vector $S$:

setsum(S) = if(#S==0,return([])); my(r=S[1]); for(i=2,#S, r=Set(concat( apply(z->apply(t->t+z,S[i]),r) )) ); r;

Finally, we are ready to compute $f_n$ for $n\leq 20000$ storing them in a vector, and print the exponents (i.e. $q$) of all $y+2$ that are powers of $2$ for $y\in f_{2n}$ when $n$ is a perfect number:

f=vector(20000); f[1]=[1]; for(n=2,#f, r=is[n]; f[n]=if(!r,[1],Set(concat(apply(t->setsum(apply(z->f[z],divisors(t))),r)))); if(n%2==0 && sigma(n/2)==n, print(n/2," ",apply(t->valuation(t+2,2),select(t->t+2==1<<valuation(t+2,2),f[n]))) ) );

This code prints:

6 [2, 3]
28 [5]
496 [2, 7, 8]
8128 [7, 8, 9, 10, 11]

So, we see that while Mersenne exponents 3, 5, 7 do appear in $y+2=2^q$ for some $y\in f_{2n}$ for $n=6, 28, 496$, respectively, the next exponent $13$ does not arise this way from $f_{16256}$.