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]
$\endgroup$
  • $\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 Mar 18 at 16:15
  • $\begingroup$ @GerhardPaseman: Thanks for your comment. I updated the question with examples. $\endgroup$ – orgesleka Mar 18 at 16:43
  • $\begingroup$ Can you give some more entries in your list, say $n=23,29,31$? $\endgroup$ – Richard Stanley Mar 18 at 21:01
  • 2
    $\begingroup$ I don't understand why $Log(15)\neq(0, 1, 1,0, \cdots)$. $\endgroup$ – Sylvain JULIEN Mar 18 at 23:21
  • $\begingroup$ you are right. sorry for the stupid mistake. i will correct that $\endgroup$ – orgesleka Mar 19 at 5:14
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.

$\endgroup$
  • $\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$ – orgesleka Mar 21 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.