Let $L_n$ be the Laplacian matrix of the undirected graph $G_n = (V_n, E_n)$ (which is defined here: Why is this bipartite graph a partial cube, if it is? ) with sorted spectrum:
$$\lambda_1 (G_n) \ge \cdots \ge \lambda_n (G_n)$$
and sorted degree-sequences:
$$d_1(G_n) \ge \cdots \ge d_n(G_n)$$
Since $\operatorname{deg}(v) = \pi \left( \frac{n}{v} \right) + \omega(v)$ is maximized to $\pi(n)$ with $v=1$, we must have $d_1(G_n) = \pi(n)$. From theory (https://www.isid.ac.in/~rbb/laplacian.pdf) of the spectrum of the Laplacian matrix, we know that:
$$\lambda_1(G_n) \ge d_1(G_n)+1$$
and
$$d_1(G_n) \ge \frac{1}{2} \lambda_1(G_n)$$
We conclude that:
$$\lambda_1(G_n) -1 \ge \pi(n) \ge \frac{1}{2} \lambda_1(G_n)$$
In particular this shows that
$$\pi(n) \approx \lambda_1(G_n)$$
Since $L_n = M_n M_n^T$ where $M_n$ is the incidence matrix, it follows that:
$$|M|_2 = \sqrt{\lambda_{\max}(M_n^T M_n)} = \sqrt{\lambda_1(G_n)}$$
so that we get:
$$\pi(n) \approx |M_n|_2^2$$
Let $v$ be an eigenvector to the eigenvalue $\lambda$.
Since $\left < L_n x , x \right > = \sum_{ i \approx j} (x_i-x_j)^2$,
we conclude that:
$$\lambda |v|^2 = \lambda \left< v,v \right> = \left < \lambda v, v \right > =\left < L_n v , v \right > = \sum_{ i \approx j} (v_i-v_j)^2$$
Hence we get:
$$\lambda = 1/|v|^2 \sum_{i \approx j } (v_i -v_j)^2$$
which is equal to:
$$= 1/|v|^2 \sum_{i=1}^n \sum_{i \approx j } (v_i -v_j)^2$$ $$= 1/|v|^2 \sum_{i=1}^n \left (\sum_{i \le j, i \approx j } (v_i -v_j)^2 + \sum_{i > j, i \approx j } (v_i -v_j)^2\right )$$
$$= 1/|v|^2 \sum_{i=1}^n \left (\sum_{p \le n/i } (v_i -v_{pi})^2 + \sum_{q|i } (v_i -v_{i/q})^2\right )$$
where $p,q$ denote primes.
My naive question is, if it is possible to "find a vector" $v$ with unit norm and so find a lower bound for $\lambda_1(G_n)$ to get a lower bound for $\pi(n)$.
For instance, taking $w_i = 1/i$ and setting $v_i := w_i/|w|$ while observing that by the Basel problem, we have $1/|w|^2 \ge 6/\pi^2$, we can lower bound $\pi(n)$ recursively by:
$$\pi(n) \ge \frac{6/\pi^2}{2-6/\pi^2} \sum_{i=2}^n \frac{1}{i^2} \left( \pi( \frac{n}{i})+e(i) \right)$$
where we have defined $e(i) := \sum_{p|i} (1-p)^2$.
Edit:
If we allow to put $v_i = 1/i^{s/2}$ for some unspecified $s>2$, we get:
$$|v|^2 = \sum_{i=1}^n \frac{1}{i^s} \le \zeta(s)$$
Plugging this vector $v$ into the expression for the eigenvalue, we find that the largest eigenvalue, which maximizes the quadratic form of $L_n$ is $\ge$ the expression of the plugged in vector:
$$\lambda_1(G_n)\ge \cdots $$
After some arrangements we find the inequality for every $s>2$:
$$\pi(n) \ge \frac{1}{2\zeta(s)-1}\sum_{i=2}^n \frac{1}{i^s} \left( \pi(n/i)+e_s(i) \right)$$
where we have put $e_s(i) := \sum_{q|i,q \text{ prime}}(1-q^{s/2})^2$
n pi(n) s=120 s=12 s=2
2 1 1.00000000000000 0.968517462376730 0.109176592451389
3 2 2.00000000000000 1.96528527751604 0.303268312364969
4 2 2.00000000000000 1.96576575249928 0.439739052929205
5 3 3.00000000000000 2.96514588856902 0.719231129604760
6 3 3.00000000000000 2.96563696379829 0.937584314507538
7 4 4.00000000000000 3.96512804152228 1.25842981069121
8 4 4.00000000000000 3.96512815882574 1.29254749583227
9 4 4.00000000000000 3.96513191517101 1.36263617246773
10 4 4.00000000000000 3.96561993304773 1.56352110257829
11 5 5.00000000000000 4.96512687366414 1.92443545778949
12 5 5.00000000000000 4.96512699355556 1.97902375401518
13 6 6.00000000000000 5.96463464841560 2.35112858982583
14 6 6.00000000000000 5.96512268545884 2.55165702494063
15 6 6.00000000000000 5.96512645489640 2.65646655369396
16 6 6.00000000000000 5.96512645492504 2.66499597497923
17 7 7.00000000000000 6.96463444111600 3.05183621951287
18 7 7.00000000000000 6.96463444204004 3.07609768450207
19 8 8.00000000000000 7.96414246855785 3.46804467568489
20 8 8.00000000000000 7.96414258770284 3.51826590821253
21 8 8.00000000000000 7.96414634931663 3.61531176816932
22 8 8.00000000000000 7.96463439009109 3.81922837886365
23 9 9.00000000000000 8.96414244559609 4.21878581361958
24 9 9.00000000000000 8.96414244562536 4.23243288767601
25 9 9.00000000000000 8.96414245381281 4.26108082553525
26 9 9.00000000000000 8.96463049476110 4.46651370363905
27 9 9.00000000000000 8.96463049476817 4.47430133437632
28 9 9.00000000000000 8.96463061391784 4.52443344315502
29 10 10.0000000000000 9.96413867956574 4.93154140264082
30 10 10.0000000000000 9.96413868048603 4.96016993132807
31 11 11.0000000000000 10.9636467472422 5.36915612573494
32 11 11.0000000000000 10.9636467472422 5.37128848105626
33 11 11.0000000000000 10.9636505087423 5.46512621341117
34 11 11.0000000000000 10.9641385497714 5.67290173537748
35 11 11.0000000000000 10.9641385581037 5.71782010484319
36 11 11.0000000000000 10.9641385581039 5.72388547109049
37 12 12.0000000000000 11.9636466263334 6.13730508779466
38 12 12.0000000000000 11.9641346673723 6.34598056921144
39 12 12.0000000000000 11.9641384288732 6.43958101402183
40 12 12.0000000000000 11.9641384289023 6.45213632215374
41 13 13.0000000000000 12.9636464974900 6.86779973184374
42 13 13.0000000000000 12.9636464984084 6.89329902667933
43 14 14.0000000000000 13.9631545671007 7.30992965747273
44 14 14.0000000000000 13.9631546862513 7.36090881014631
45 14 14.0000000000000 13.9631546862584 7.37255431334113
46 14 14.0000000000000 13.9636427273044 7.58265217934399
47 15 15.0000000000000 14.9631507961276 8.00097299351717
48 15 15.0000000000000 14.9631507961276 8.00438476203127
49 15 15.0000000000000 14.9631507962720 8.01984500419432
50 15 15.0000000000000 14.9631507962740 8.02788040139874
51 15 15.0000000000000 14.9631545577754 8.12156827312173
52 15 15.0000000000000 14.9631546769260 8.17292649264768
53 16 16.0000000000000 15.9626627458444 8.59330884364598
54 16 16.0000000000000 15.9626627458444 8.59600456197811
55 16 16.0000000000000 15.9626627540330 8.63382838640424
56 16 16.0000000000000 15.9626627540621 8.64636141359892
57 16 16.0000000000000 15.9626665155635 8.74018137239371
58 16 16.0000000000000 15.9631545566120 8.95178404266216
59 17 17.0000000000000 16.9626626255732 9.37381226099766
60 17 17.0000000000000 16.9626626255735 9.38096939316948
61 18 18.0000000000000 17.9621706945433 9.80347488397840
62 18 18.0000000000000 17.9626587355920 10.0154660614126
63 18 18.0000000000000 17.9626587355991 10.0262489347412
64 18 18.0000000000000 17.9626587355991 10.0267820235715
65 18 18.0000000000000 17.9626587437872 10.0633723324262
66 18 18.0000000000000 17.9626587447055 10.0873330354527
67 19 19.0000000000000 18.9621668136920 10.5111006778838
68 19 19.0000000000000 18.9621669328426 10.5630445583753
69 19 19.0000000000000 18.9621706943441 10.6571551938344
70 19 19.0000000000000 18.9621706943462 10.6688304049455
71 20 20.0000000000000 19.9616787633392 11.0933218177698
72 20 20.0000000000000 19.9616787633392 11.0948381593316
73 21 21.0000000000000 20.9611868323345 11.5196619200882
74 21 21.0000000000000 20.9616748733837 11.7325921624880
75 21 21.0000000000000 20.9616748733837 11.7367845436381
76 21 21.0000000000000 20.9616749925343 11.7889534139923
77 21 21.0000000000000 20.9616749926794 11.8114921471953
78 21 21.0000000000000 20.9616749935977 11.8352511558090
79 22 22.0000000000000 21.9611830625981 12.2609716419325
80 22 22.0000000000000 21.9611830625981 12.2641104689655
81 22 22.0000000000000 21.9611830625981 12.2649757612696
82 22 22.0000000000000 21.9616711036473 12.4783929431823
83 23 23.0000000000000 22.9611791726498 12.9046396597700
84 23 23.0000000000000 22.9611791726500 12.9110144834789
85 23 23.0000000000000 22.9611791808380 12.9464345433690
86 23 23.0000000000000 22.9616672218872 13.1600640249748
87 23 23.0000000000000 22.9616709833887 13.2545712298555
88 23 23.0000000000000 22.9616709834178 13.2673160180238
89 24 24.0000000000000 23.9611790524224 13.6942638942736
90 24 24.0000000000000 23.9611790524224 13.6974448419055
91 24 24.0000000000000 23.9611790525669 13.7184337484606
92 24 24.0000000000000 23.9611791717176 13.7709582149613
93 24 24.0000000000000 23.9611829332191 13.8655804530253
94 24 24.0000000000000 23.9616709742684 14.0795843667032
95 24 24.0000000000000 23.9616709824563 14.1147144303574
96 24 24.0000000000000 23.9616709824563 14.1155673724859
97 25 25.0000000000000 24.9611790514625 14.5433159009297
98 25 25.0000000000000 24.9611790514626 14.5474083179729
99 25 25.0000000000000 24.9611790514696 14.5578347326790
suggest the following, which I do not see how to approach:
Edit (11.05.2024):
Question: Is $$\pi(n) = \lim_{s \rightarrow \infty} \frac{1}{2\zeta(s)-1}\sum_{i=2}^n \frac{1}{i^s} \left( \pi(n/i)+e_s(i) \right)$$ ?
