10
$\begingroup$

Let $Log(n) = \sum_{i=1}^r \alpha_i \cdot e_i$, where $n = \prod_{i=1}^r p_i^{\alpha_i}$ and $p_i$ is the $i$-th prime, $\alpha_i \ge 0$, $e_i$ is the $i$-th standard basis vector. For example $6 = 2\cdot3$, hence: $$Log(6) = (1,1,0,0,0,\cdots)$$ $$Log(15) = (0,1,1,0,0,\cdots)$$ $$Log(7) = (0,0,0,1,0,\cdots)$$ Consider the matrix $A_n = (Log(1)^T,Log(2)^T,\cdots,Log(n)^T)$. Then one can think about that $rank(A_n) = \Pi(n)$, where $\Pi$ is the prime counting function. For fun, we might compute the Smith normal form of this matrix: $$D_n = U_n A_n V_n$$ I conjecture that $V_n = 1_n$ and that $D_n$ consists of $\Pi(n)$ ones on the diagonal. Now the mysterious part is the irreducible factors of the characteristic polynomial of $U_n$.

Here is a list for $1 \le n \le 20$ computed with SAGEMATH:

1 x - 1
2 x^2 + 1
3 (x - 1) * (x^2 + x + 1)
4 (x - 1)^2 * (x^2 + x + 1)
5 (x - 1) * (x^4 + 1)
6 (x - 1)^2 * (x^4 + 1)
7 (x - 1) * (x^2 + 1) * (x^4 + 1)
8 (x - 1)^2 * (x^2 + 1) * (x^4 + 1)
9 (x - 1)^3 * (x^2 + 1) * (x^4 + 1)
10 (x - 1)^4 * (x^2 + 1) * (x^4 + 1)
11 (x - 1)^5 * (x^2 + 1) * (x^4 + x^3 + x^2 + x + 1)
12 (x - 1)^6 * (x^2 + 1) * (x^4 + x^3 + x^2 + x + 1)
13 (x - 1)^5 * (x^2 + 1)^2 * (x^4 + x^3 + x^2 + x + 1)
14 (x - 1)^6 * (x^2 + 1)^2 * (x^4 + x^3 + x^2 + x + 1)
15 (x - 1)^7 * (x^2 + 1)^2 * (x^4 + x^3 + x^2 + x + 1)
16 (x - 1)^8 * (x^2 + 1)^2 * (x^4 + x^3 + x^2 + x + 1)
17 (x - 1)^9 * (x^2 + 1) * (x^2 + x + 1) * (x^4 + x^3 + x^2 + x + 1)
18 (x - 1)^10 * (x^2 + 1) * (x^2 + x + 1) * (x^4 + x^3 + x^2 + x + 1)
19 (x - 1)^9 * (x^2 + x + 1) * (x^2 + 1)^2 * (x^4 + x^3 + x^2 + x + 1)
20 (x - 1)^10 * (x^2 + x + 1) * (x^2 + 1)^2 * (x^4 + x^3 + x^2 + x + 1)

It occurs that the irreducible factors are cyclotomic polynomials $p(x)$ with $\deg(p(x))=\phi(m)$ for some number $m$. But how does one compute the numbers $m$, given $n$? I think this would give an interesting decomposition of $n$ in summands and products.

For example: $$ 13 = 5\cdot\phi(1)+2\phi(4)+1\phi(5)$$ $$ 5 = 1\cdot\phi(1) + 1\cdot \phi(8)$$

I have tried to search OEIS for various related sequences but without success.

Thanks for you help.

Edit: Here is some sage code, to get the matrix $U_5,\cdots,U_{10}$ and the corresponding matrices.

MAXN=100

def Log(a,N=MAXN):
    return vector([valuation(a,p) for p in primes(N)])

def Exp(v,N=MAXN):
    P = list(primes(N))
    return prod([P[i]**v[i] for i in range(len(P))])


def AA(n,N=MAXN):
    return matrix([Log(n,N=N) for n in range(1,n+1)],ring=QQ)


def UU(n,N=MAXN):
    D,U,V = (AA(n,N=N)).smith_form()
    return U


[ 0  1  0  0  0]
[ 0  0  1  0  0]
[ 0  0  0  0  1]
[ 0 -2  0  1  0]
[-1  0  0  0  0]
[ 0  1  0  0  0  0]
[ 0  0  1  0  0  0]
[ 0  0  0  0  1  0]
[ 0 -2  0  1  0  0]
[-1  0  0  0  0  0]
[ 0 -1 -1  0  0  1]
[ 0  1  0  0  0  0  0]
[ 0  0  1  0  0  0  0]
[ 0  0  0  0  1  0  0]
[ 0  0  0  0  0  0  1]
[-1  0  0  0  0  0  0]
[ 0 -1 -1  0  0  1  0]
[ 0  2  0 -1  0  0  0]
[ 0  1  0  0  0  0  0  0]
[ 0  0  1  0  0  0  0  0]
[ 0  0  0  0  1  0  0  0]
[ 0  0  0  0  0  0  1  0]
[-1  0  0  0  0  0  0  0]
[ 0 -1 -1  0  0  1  0  0]
[ 0  2  0 -1  0  0  0  0]
[ 0 -3  0  0  0  0  0  1]
[ 0  1  0  0  0  0  0  0  0]
[ 0  0  1  0  0  0  0  0  0]
[ 0  0  0  0  1  0  0  0  0]
[ 0  0  0  0  0  0  1  0  0]
[-1  0  0  0  0  0  0  0  0]
[ 0 -1 -1  0  0  1  0  0  0]
[ 0  2  0 -1  0  0  0  0  0]
[ 0 -3  0  0  0  0  0  1  0]
[ 0  0 -2  0  0  0  0  0  1]
[ 0  1  0  0  0  0  0  0  0  0]
[ 0  0  1  0  0  0  0  0  0  0]
[ 0  0  0  0  1  0  0  0  0  0]
[ 0  0  0  0  0  0  1  0  0  0]
[-1  0  0  0  0  0  0  0  0  0]
[ 0 -1 -1  0  0  1  0  0  0  0]
[ 0  2  0 -1  0  0  0  0  0  0]
[ 0 -3  0  0  0  0  0  1  0  0]
[ 0  0 -2  0  0  0  0  0  1  0]
[ 0 -1  0  0 -1  0  0  0  0  1]

Update: Here are the matrices and corresponding characteristic polynomials for $n=23,29,31$:

[ 0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1]
[ 0 -1  0  0 -1  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -2 -1  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0]
[ 0  1  1  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -1  0  0  0  0 -1  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0]
[ 0  0 -1  0 -1  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0]
[ 0 -4  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0]
[ 0 -2  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -1 -2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0]
[ 0  3  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -2  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0]
[ 0  0 -1  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0]
[ 0 -1  0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  1  0]
[ 0  0  2  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
23 (x - 1)^11 * (x^2 + x + 1) * (x^2 + 1)^3 * (x^4 + x^3 + x^2 + x + 1)
[ 0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1]
[ 1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -2 -1  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  1  1  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -1  0  0  0  0 -1  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0 -1  0 -1  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -4  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -2  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -1 -2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0]
[ 0  3  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -2  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0]
[ 0  0 -1  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0]
[ 0 -1  0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0]
[ 0  0  2  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -3 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0]
[ 0  0  0  0 -2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0]
[ 0 -1  0  0  0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0]
[ 0  0 -3  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0]
[ 0 -2  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0]
[ 0  1  0  0  1  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
29 (x - 1)^15 * (x^2 + x + 1) * (x^2 + 1)^4 * (x^4 + x^3 + x^2 + x + 1)
[ 0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1]
[ 0 -2 -1  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  1  1  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -1  0  0  0  0 -1  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0 -1  0 -1  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -4  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -2  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -1 -2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  3  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -2  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0 -1  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0]
[ 0 -1  0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0]
[ 0  0  2  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -3 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0]
[ 0  0  0  0 -2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0]
[ 0 -1  0  0  0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0]
[ 0  0 -3  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0]
[ 0 -2  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0]
[ 0  1  0  0  1  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0 -1 -1  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0]
[-1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
31 (x - 1)^15 * (x^2 + x + 1) * (x^2 + 1)^5 * (x^4 - x^2 + 1)

Update to the answer given by Denis Serre: I can not see how, $D_4 = U_1 \cdot A_4$ or $D_4 = U_2 \cdot A_4$:

sage: AA(4)
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
sage: U1
[0 1 0 0]
[0 0 1 0]
[1 0 0 0]
[0 0 0 1]
sage: U2
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]
[1 0 0 0]
sage: U1*AA(4)
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
sage: U2*AA(4)
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
sage: UU(4)*AA(4)
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
Improve this question
$\endgroup$
12
  • $\begingroup$ Just doing column reduction allows you to reduce A_n to a matrix of all ones, and then you use an appropriate permutation, so you should (in principle) be able to write down U_n explicitly, and maybe even represent it as a convolution. I am not surprised that the associated polynomial is a product of cyclotomics; I am surprised that 8 appears in the representation for five through ten. It might help for you to list U_5 through U_10 to show us why. Gerhard "Sometimes Having Enough Examples Helps" Paseman, 2019.03.18. $\endgroup$
    – Gerhard Paseman
    Commented Mar 18, 2019 at 16:15
  • $\begingroup$ @GerhardPaseman: Thanks for your comment. I updated the question with examples. $\endgroup$
    – user6671
    Commented Mar 18, 2019 at 16:43
  • $\begingroup$ Can you give some more entries in your list, say $n=23,29,31$? $\endgroup$
    – Richard Stanley
    Commented Mar 18, 2019 at 21:01
  • 2
    $\begingroup$ I don't understand why $Log(15)\neq(0, 1, 1,0, \cdots)$. $\endgroup$
    – Sylvain JULIEN
    Commented Mar 18, 2019 at 23:21
  • $\begingroup$ you are right. sorry for the stupid mistake. i will correct that $\endgroup$
    – user6671
    Commented Mar 19, 2019 at 5:14

1 Answer 1

Reset to default
6
$\begingroup$

I made hand calculations for $n\le4$. It turns out that even with $V_n=1_n$, the factor $U_n$ is not unique. In other words, the factorisation problem is underdetermined. This is due to the fact that the few last columns of $A_n$ vanish. For instance, if $n=3$, the general $U_3$ is $$\begin{pmatrix} a & 1 & 0 \\ b & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}.$$ Therefore the characteristic polynomial can be any of the polynomials $X^3-aX^2-bX-1$. You may prefer to select the "simplest" matrix $U_n$, which gives you here the polynomial $X^3-1$, but how will you proceed for higher values of $n$ ?

Edit (after miscalculation in my original answer.) The case $n=4$ yields even more freedom. You may choose the matrices $$U_4=\begin{pmatrix} a & 1 & 0 & 0 \\ b & 0 & 1 & 0 \\ c & -2 & 0 & 1 \\ -1 & 0 & 0 & 0 \end{pmatrix}$$ and even this list is incomplete. What is the simplest among them ? At least the second and third columns are mandatory. The corresponding characteristic polynomial $X^4-aX^3+(2-b)X^2-(2a+c)X+1$ can be any polynomial $X^4+\cdots+1$ with integer coefficients.

Improve this answer
$\endgroup$
1
  • $\begingroup$ thanks for the update. i see know that the choice of Un is a particular choice of the algorithm and has not much to do with the decomposition of n $\endgroup$
    – user6671
    Commented Mar 21, 2019 at 20:06

You must log in to answer this question.