1
$\begingroup$

Are there any heuristics to compute the spectral norm of the adjacency matrix of this directed graph connected to prime numbers?

Let $p$ be a prime and $n$ be a natural number.

Define inductively for prime numbers: $f_1(x) := 1$, $f_2(x):=x$, $f_p(x) := 1+\prod_{q\mid p-1} f_q(x)^{v_q(p-1)}$.

Then $f_p(x)$ always irreducible for each prime $p$, as is being shown here.

Let $f_n(x):= \prod_{p\mid n} f_p(x)^{v_p(n)}$ for each natural number $n$.

Define a directed edge between the primes $p \rightarrow q$ if $f_p(x)$ is irreducible $\mod q$.

The graph $G_n$ contains as vertices all primes $p \le p_n$ where $p_n$ is the $n$-th prime and might have loops.

Question: I am asking for heuristics to approximately compute the spectral norm $|A_n|_2$ of the adjacency matrix $A_n$ of the graph $G_n$?

I do not have a guess for a formula, but asking ChatGPT, it suggested a heuristic based on random polynomials of degree $d$ being irreducible in a finite field. I think I can prove inductively by the definition of $f_n(x)$, that the degree $d_n$ of $f_n(x)$ satisfies:

$$ \frac{\log(n)}{\log(3)} \le d_n \le \frac{\log(n)}{\log(2)}$$

which might be of help in this setting, but I am not sure.

Below is some sage-math code to test these ideas:

def ff(n,x):
    if n==1:
        return 1
    if n==2:
        return x
    if is_prime(n):
        return 1+ff(n-1,x)
    return prod([ff(p,x)**valuation(n,p) for p in prime_divisors(n)])

def is_irred(pol,ring):
    ll = list(factor(ring(pol)))
    degs = sum([l[1] for l in ll])
    if degs==1:
        return True
    return False    

def compute_graph(N):
    G = DiGraph(loops=True,weighted=True)
    var("x")

    ll = dict([])
    for p in primes(N):
        G.add_vertex(p)
        fp = ff(p,x)
        Kp = Zmod(p)
        Rp = Kp[x]
        ll[p] = (fp,Rp)
    for p in primes(N):    
        for q in primes(N):
            fp = ll[p][0]
            Rq = ll[q][1]
            if is_irred(fp,Rq):
                G.add_edge((p,q,fp.degree(x)))
    return G,ll 


def add_prime(G,ll,p):
    var("x")
    G.add_vertex(p)
    fp = ff(p,x)
    Kp = Zmod(p)
    Rp = Kp[x]
    ll[p] = (fp,Rp)
    for q in G.vertices():
        Rq = ll[q][1]
        fq = ll[q][0]
        if is_irred(fp,Rq):
            G.add_edge((p,q,fp.degree(x)))
        if is_irred(fq,Rp):
            G.add_edge((q,p,fq.degree(x)))
    return G,ll
    
pp = []

G,ll = compute_graph(2)
var("x")
for n in range(2,151):
    #print(n)
    print(n,RDF(log(n+0.0)/log(3.0))<=RDF(ff(n,x).degree(x))<=RDF(log(n+0.0)/log(2.0)))
    #continue
    p = nth_prime(n)
    G,ll = add_prime(G,ll,p)
    A = G.adjacency_matrix()
    print((n,p,A.norm(2)))
    pp.append((n,A.norm(2)))
    if n%50!=0:
        continue
    rr = (A.charpoly().roots(ring=CC))
    pt = [(real(x),imag(x)) for x,y in rr]
    points(pt).show(aspect_ratio=1)
    matrix_plot(G.weighted_adjacency_matrix(sparse=False), cmap='winter', colorbar=True,dpi=300).show()
    
(line(pp)).show()

Edit: These polynomials can be used in theory and heuristically to count primes: https://www.orges-leka.de/counting_primes_with_polynomials.pdf

$\endgroup$
2
  • $\begingroup$ What is the definition of $v_q$? $\endgroup$ Commented Sep 22 at 20:07
  • $\begingroup$ The valuation of $n$ with respect to the prime $q$: $a=v_q(n)$ iff $q^a$ divides $n$ , but $q^{a+1}$ does not divide $n$. $\endgroup$ Commented Sep 22 at 20:19

0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.