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