Is the A123706 triangle an extension of the Moebius function?

[Peter Luschny]

Paul D. Hanna's A123706 is defined, in Sage parlance, as

def A123706_triangle(dim) :
m = matrix(QQ, dim, dim, lambda n, k: (n+1)//(k+1))
return m.inverse()

This triangle gives rise to some interesting arithmetical
functions and open questions. It is the purpose of this
thread to explore these relations.

http://oeis.org/A123706
-----------------------

In response to Mats Granvik's
http://list.seqfan.eu/pipermail/seqfan/2012-February/016393.html

Let me see if I understand this. You replace the dependency
of A123706 from A010766 by applying a recursion (according
to Wikipedia invented by you (see also [1] and [2])). Further
you indicate that applying the same recursion to different
initial values will also lead to other highly significant
arithmetical functions.

[1] http://math.stackexchange.com/questions/48946/do-these-series-converge-to-the-mangoldt-function
[2] http://math.stackexchange.com/questions/84177/is-this-sum-equal-to-the-mobius-function

[Enrique Pérez Herrero]

Hello Peter, hello all:

If you add all the elements from matrix T(n) (this is the triangle
A123706) then you have:

http://oeis.org/A002321

This is the Mertens function...

T[n_]:=Inverse[Table[Floor[i/j], {i, 1, n}, {j, 1, n}]];
A002321[n_]:=Plus @@ Flatten[T[n]];
Table[A002321[n], {n, 1, 10}]

[Peter Luschny]

Hello Enrique!

def A123706_triangle(dim) :
m = matrix(QQ, dim, dim, lambda n, k: (n+1)//(k+1))
return m.inverse()

def A002321(M, m) :
return add(add(M[n,k] for k in (0..m)) for n in (0..m))

dim = 25
M = A123706_triangle(dim)
[A002321(M, m) for m in range(dim)]

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

Bravo Enrique! So it took you two minutes to answer the question
affirmatively. You are very quick :)

OK, next the details...

[Enrique Pérez Herrero]

One of my hundred unconcluded projects is about these "number
theoretic matrix algebra":
There must be a nice theorems combining: Matrix algebra, number
theory, arithmetic functions, Dirichlet convolutions, matrix norms,
eigenvalues... Hadamard products...Group theory... and Riemann H.

In this example it is shown a relationship between: Moebius-Mertens,
Redheffer Matrix (Also determinant of n X n (0,1) matrix defined by
A(i,j)=1 if j=1 or i divides j.), matrix inversion, divisor set and
characteristic functions (1 is a divisor, 0 it is not)...

Later before I was reading the interesting...

http://www.emis.de/journals/AUSM/C1-1/MATH1-4.PDF

in order to prove the formula for the determinant in:

http://oeis.org/A175836

If you want to find more "curios" about A123706, try distict matrix
norms, transpose the triangle an multiple for the same triangle but
without trasposing... what about to power the matrix...

Regards...

[Enrique Pérez Herrero]

I meant "distinct", "multiply" and "transposing", this is the problem
with english, the writing has nothing in common with talking...

[Peter Luschny]

> One of my hundred unconcluded projects ...
I can also offer a handful ... ;-))

> http://www.emis.de/journals/AUSM/C1-1/MATH1-4.PDF
Thanks, looks interesting.

> If you want to find more "curios" about A123706

First, your observation does not answer the question I posed
on the list, when I wrote: "I think the real question is:
what is the meaning of A123706(n,k) in arithmetical terms?"

Second, I am still interested in an (outline of a) proof of

A123712 = A178212

which was the starting point of my investigation.
http://oeis.org/search?q=A123712+A178212

Now that we know (or have good reason to assume) that the partial
triangles sum to Mertens function can we give a more precise
description of the relation between these two viewpoints?

Cheers, Peter

[Enrique Pérez Herrero]

Hola amigos:

if T(i,j) is an element of matrix A123706, and m(i,j)=mu(i/j) if j
divides i and 0 otherwise, (or moebius mu being zero for non integers)
then:

T(i,j)=m(i, j) - m(i,j+1)

Note that:

a) if you add all elements in the same row "i" then it gives mu(i),
here comes also the Mertens function observation for the whole matrix.
b) First column of T (or A123706) is A092673.

----------------------
I need to go urgently.
Best regards all.

[Peter Luschny]

On 11 Feb., 14:35, Enrique Pérez Herrero <psychgeome...@gmail.com>
wrote:

> if T(i,j) is an element of matrix A123706, and m(i,j)=mu(i/j) if j
> divides i and 0 otherwise, (or moebius mu being zero for non integers)
> then:
> T(i,j)=m(i, j) -  m(i,j+1)

Congratulation Enrique! Did you read Mats Granvik message on the
seqfan list?
His message has the timestamp Sat Feb 11 14:30:18 CET 2012, yours
14:35.
Was this a photo-finish between Newton and Leibniz?

So the most important question is solved. Perhaps someone
can add a clever recursion?

> Note that:
> a) if you add all elements in the same row "i" then it gives mu(i),
> here comes also the Mertens function observation for the whole matrix.
> b) First column of T (or A123706) is A092673.

I looked more closely at the borders of the triangle and the
corner case (0,0) and submitted a new variant of A123706 to
the OEIS. It looks like this:

[ 0] -1,
[ 1] 1, -1,
[ 2] -1, 2, -1,
[ 3] -1, 1, 1, -1,
[ 4] 0, -1, 1, 1, -1,
[ 5] -1, 1, 0, 0, 1, -1,
[ 6] 1, -2, 0, 1, 0, 1, -1,
[ 7] -1, 1, 0, 0, 0, 0, 1, -1,
[ 8] 0, 0, 0, -1, 1, 0, 0, 1, -1,
[ 9] 0, 0, -1, 1, 0, 0, 0, 0, 1, -1,

See the differences? The left border now became the Möbius function
itself, not included in A123706. And the signs of the other entries
flipped. I believe this is the one and only true MOEBIUS TRIANGLE ;-)

The inverse of this triangle as a matrix begins

[-1, 0, 0, 0, 0, 0, 0]
[-1, -1, 0, 0, 0, 0, 0]
[-1, -2, -1, 0, 0, 0, 0]
[-1, -3, -1, -1, 0, 0, 0]
[-1, -4, -2, -1, -1, 0, 0]
[-1, -5, -2, -1, -1, -1, 0]
[-1, -6, -3, -2, -1, -1, -1]

As a side remark: If you read A008683 (Moebius function) you find the
remark: "Note that Maple defines mobius(0) to be -1. This is unwise!
Moebius(0) is better left undefined."

I do understand that arithmetical functions are defined only for n>=1.
However, if you think that the triangle above makes sens, then there
should be a -1 at the top. '0' is excluded (as the triangle would not
be invertible) and '1' would give an inconsistent mix of signs in the
inverse matrix. Thus we arrive at precisely the values Maple gives!

Cheers, Peter

[George Beck]

I made a kind of companion matrix that seems to have connections to evil
and odius numbers and twin primes.

g[m_] := PadRight[#, m] & /@
Table[Mod[n, k, 1], {n, 3, m + 2}, {k, 2, n - 1}]

Please see attached Mathematica notebook and corresponding pdf for details.

- George

[Peter Luschny]

Hi George,

wow, thanks for this nice worksheet. Your idea to use
the fractional part instead of floor is nicely complementing
what has been said.

Well, as soon as it is clear that the Möbius function is powering
the engine behind the scenes it is clear that there is a goldmine
to be explored.

With respect to evil numbers and twin primes I hope that others
will turn in and comment.

Cheers, Peter

[George Beck]

With f the original matrix, the differences of the first column of the
product of f and g seems to be A069735 (to 88 terms), a multiplicative
function.

In[45]:= fg100 = f[100].g[100];

Differences@First@Transpose[fg100]

Out[49]= {3, 2, 5, 2, 6, 2, 7, 3, 6, 2, 10, 2, 6, 4, 9, 2, 9, 2, 10, 4,
6, 2, 14, 3, 6, 4, 10, 2, 12, 2, 11, 4, 6, 4, 15, 2, 6, 4, 14, 2, 12, 2,
10, 6, 6, 2, 18, 3, 9, 4, 10, 2, 12, 4, 14, 4, 6, 2, 20, 2, 6, 6, 13, 4,
12, 2, 10, 4, 12, 2, 21, 2, 6, 6, 10, 4, 12, 2, 18, 5, 6, 2, 20, 4, 6,
4, 14, 2, 18, 4, 10, 4, 6, 4, 22, 2, 9, 6, 15}

Following a reference in A069735 leads to
A051731 Triangle read by rows: T(n,k)=1 if k divides n, T(n,k)=0
otherwise. There Paul Barry suggests calling this a Mobius matrix.
Perhaps that helps lead back to the Mobius function again.

1 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0 0 0
1 1 0 1 0 0 0 0 0 0 0 0
1 0 0 0 1 0 0 0 0 0 0 0
1 1 1 0 0 1 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0 0 0 0
1 1 0 1 0 0 0 1 0 0 0 0
1 0 1 0 0 0 0 0 1 0 0 0
1 1 0 0 1 0 0 0 0 1 0 0
1 0 0 0 0 0 0 0 0 0 1 0
1 1 1 1 0 1 0 0 0 0 0 1

[George Beck]

The first column of the inverse of f is A092673 a(n) = moebius(n)-
moebius(n/2) where moebius(n) is zero if n is not an integer.

(In the definitions, I would drop the first column, which is rather dull
both for the Mobius matrix and f.)

[Peter Luschny]

> First, the question I posed on the list was:

> "I think the real question is: what is the meaning of
> A123706(n,k) in arithmetical terms?"

OK, this first question was very nicely answered by Mats and
Enrique. What about part 2?

> Second, I am still interested in an (outline of a) proof of
> A123712 = A178212
> which was the starting point of my investigation.
> http://oeis.org/search?q=A123712+A178212

The essence of part 1 is the extension of the one parameter
Möbius function to a bivariate Möbius function:

/
| def Moebius(n,k) : return moebius(n//k) if k<>0 and n%k == 0 else 0
\

Now Paul looked at the number of k such that the first forward
difference in k does not vanish: Moebius(n, k+1) <> Moebius(n,k).

def A123709(n) :
return len([k for k in (1..n-1) if Moebius(n,k+1) <> Moebius(n,k)])+1

Et voilà, three more of Paul's sequences are easily described:

def list(n,m) : return [i for i in (1..n) if A123709(i) == m]
def A123710_list(n) : return list(n,4)
def A123711_list(n) : return list(n,8)
def A123712_list(n) : return list(n,16)

In particular A123712(n) now simply means
card {0<k<n | Moebius(n, k+1) <> Moebius(n, k)} = 15.

On the other hand Reinhard found in A178212 a sequence
with the description: {n | Omega(n) > 3 and omega(n) = 3}
which is by numerical experiment equal to A123712.

So now we can formulate the A123712/A178212-conjecture:

/
| Let n>=1 be an integer. Then Omega(n) > 3 and omega(n) = 3
| if and only if
| card { 0<k<n | Moebius(n,k+1) <> Moebius(n,k)} = 15.
\

Of course this '15' looks rather strange here. On the other hand we
certainly see here only the tip of an iceberg and the strangeness
will go away as soon as the general relation is found.

Any idea how this general relation might look like?

Peter

[Peter Luschny]

> With f the original matrix, the differences of the first column of the
> product of f and g seems to be A069735 (to 88 terms), a multiplicative
> function.

A069735 Number of regular orientable coverings of the Klein bottle
with 2n lists.

Wow, this sounds exotic and spectacular. Or is it just another
'pimp up my sequence'-name? The formula says:
"a(n) = d(n) + d(n/2) for even n and d(n) otherwise
where d(n) is the number of divisors of n."

> Following a reference in A069735 leads to
> A051731 Triangle read by rows: T(n,k)=1 if k divides n, T(n,k)=0
> otherwise. There Paul Barry suggests calling this a Mobius matrix.
> Perhaps that helps lead back to the Mobius function again.

Well, it does. Paul D. Hanna points there to the matrix inverse which
is A054525 and looks like a better candidate for this name.

[Enrique Pérez Herrero]

Peter:

I haven't read Mats Granvik message, I've just suscribed to seqfan
right now.

I think that we must use the "true" meaning of mu, not the formal
definition that cames in all books:

mu(n)=((-1)*[omega(n)==Omega(n)])^omega(n), where [] means Iverson
bracket, an amazing notation that you teach me that it existed.

Best Regards, Enrique.

[Peter Luschny]

On 12 Feb., 23:13, Enrique Pérez Herrero <psychgeome...@gmail.com>
wrote:

> I think that we must use the "true" meaning of mu, not the formal
> definition that cames in all books:
> mu(n)=((-1)*[omega(n)==Omega(n)])^omega(n), where [] means Iverson
> bracket, an amazing notation that you teach me that it existed.

C'est absolument génial !

BRAVO!

[George Beck]

Let i be the matrix with all ones on and below the main diagonal and f
(the matrix of this thread). Then it seems that the sequence of the row
sums of i.f is A032741 a(0) = 0; for n > 0, a(n) = number of proper
divisors of n.

The sequence of partial sums of A03274 seems to be A002541
Sum_{k=1..n-1} floor((n-k)/k). The conjecture is that a(n) = A002541(n)
- A002541(n-1). To relate these two sequences in this way is probably
easier to prove than to find in the literature. So far I could do neither.

A032741 and A002541 are not cross-referenced yet--I couldn't login to OEIS.

[George Beck]

Proof

short version: floor((n-k)/k) - floor((n-k-1)/k) only increases by 1
when k | n.

long version:

If k | (n-k), say (n-k)/k = m, then (n-k-1)/k = m - 1/k, and
floor((n-k)/k) - floor((n-k-1)/k) = m - (m-1) = 1.

If k does not divide n-k, (n-k)/k = m + j/k and (n-k-1)/k = m + (j-1)/k,
where m is an integer and j is one of 1, 2, 3, ..., k-1. Then
floor((n-k)/k) - floor((n-k-1)/k) = m - m = 0.

[M. Hasler]

On Feb 12, 6:08 am, Peter Luschny <peter.lusc...@googlemail.com>
wrote:

> Et voilà, three more of Paul's sequences are easily described:
>
> def list(n,m)       : return [i for i in (1..n) if A123709(i) == m]
> def A123710_list(n) : return list(n,4)
> def A123711_list(n) : return list(n,8)
> def A123712_list(n) : return list(n,16)
>
> In particular A123712(n) now simply means
>    card {0<k<n | Moebius(n, k+1) <> Moebius(n, k)} = 15.
>
> On the other hand Reinhard found in A178212 a sequence
> with the description: {n | Omega(n) > 3 and omega(n) = 3}
> which is by numerical experiment equal to A123712.
>
> So now we can formulate the A123712/A178212-conjecture:
>
> /
> | Let n>=1 be an integer. Then Omega(n) > 3 and omega(n) = 3
> | if and only if
> | card { 0<k<n | Moebius(n,k+1) <> Moebius(n,k)} = 15.
> \
>
> Of course this '15' looks rather strange here. On the other hand we
> certainly see here only the tip of an iceberg and the strangeness
> will go away as soon as the general relation is found.
>
> Any idea how this general relation might look like?

What did you mean by "general relation" ?
Obviously, you have, along the same lines of reasoning:

| Omega(n) > m and omega(n) = m
| if and only if
| card { 0<k<n | Moebius(n,k+1) <> Moebius(n,k)} = 2^(m+1)-1.

with the only exception (of the "only if" part) of n=6,
[the "next" example (m=3) is A123709(420)=32]
and also

| For odd n, Omega(n) = omega(n) = m
| if and only if
| card { 0<k<n | Moebius(n,k+1) <> Moebius(n,k)} = 2^(m+1)-2.

e.g. A123709(105)=15.
See http://oeis.org/A123709/b123709.txt
(500 values computed using the original definition in terms of the
matrix inverse.)

Maximilian

[Peter Luschny]

> I think that we must use the "true" meaning of mu, not the formal
> definition that cames in all books:
> mu(n)=((-1)*[omega(n)==Omega(n)])^omega(n),
> where [] means Iverson bracket

Enrique, I played a little with your idea. See the pdf.

[M. Hasler]

On Feb 13, 3:48 pm, Peter Luschny <peter.lusc...@googlemail.com>
wrote:
> > mu(n)=((-1)*[omega(n)==Omega(n)])^omega(n),

> Enrique, I played a little with your idea. See the pdf.

Why did you put "//" in your code?
He wrote (here in PARI)

Moebius(n)=(-(omega(n)==bigomega(n)))^omega(n)

vector(40,n,Moebius(n))
= [1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, -1, 1, 1, 0, -1, 0, -1,
0, 1, 1, -1, 0, 0, 1, 0, 0, -1, -1, -1, 0, 1, 1, 1, 0, -1, 1, 1, 0]

vector(40,n,moebius(n))
= [1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, -1, 1, 1, 0, -1, 0, -1,
0, 1, 1, -1, 0, 0, 1, 0, 0, -1, -1, -1, 0, 1, 1, 1, 0, -1, 1, 1, 0]


Am I missing something ?

Maximilian

[Enrique Pérez Herrero]

Peter, I'm sorry but I'm in a very busy situation: a 10 in Richter
scale ...

Nice!, someday I will show you a generalization of trig functions:
cos_4, sin_infinity... another book that need to be written.

With this mu_LP (Luschny-Pérez mu (This is a joke of course)), How
does Dirichlet behave? I mean convolution, series... Mertens_LP,
sum(n=1, inf, mu_LP(n)/n^s), mu_LP is multiplicative?

I will be waiting news from non-zero-convoluted, Number Theory (all
compiled in a book)

Regards.

[Peter Luschny]

> > > mu(n)=((-1)*[omega(n)==Omega(n)])^omega(n),
> > Enrique, I played a little with your idea. See the pdf.
>
> Why did you put "//" in your code?
> He wrote (here in PARI)
>  Moebius(n)=(-(omega(n)==bigomega(n)))^omega(n)

Yes Maximilian, I am well aware of this. To play is to
play and to enter variations, isn't it?

If omega(n) = Omega(n) then [omega(n)==Omega(n)] = 1.
If omega(n) = Omega(n) then omega(n)//Omega(n) = 1.

> Am I missing something ?

Nothing important ...

Peter

[Peter Luschny]

> What did you mean by "general relation" ?

Exactly what you did, Maximilian! Looking for a, b, and c(a,b)

| Omega(n) > a and omega(n) = b
| if and only if
| card { 0<k<n | Moebius(n,k+1) <> Moebius(n,k)} = c(a,b).

and yes, for variations like

| For odd n, Omega(n) = omega(n) = m

In fact when I stumbled over A123712/A178212 I was looking for

Omega(n) > 3 and omega(n) >= 3 (not in OEIS)

although I did not knew this at that time.

> (500 values computed using the original definition in terms of the
> matrix inverse.)

My good old Maple, now in retirement, would say: 'object too large'
and quit ;-))

I will be offline for the next couple of days:

By Roberta F. (Own work) [CC-BY-SA-3.0
(www.creativecommons.org/licenses/by-sa/3.0)]
via Wikimedia Commons from Wikimedia Commons

[Enrique Pérez Herrero]

Peter: Have a nice vacation!

There is an arithmetical function I call "Squarefreeness Index":
S(n)=omega(n)/Omega(n) (S(n)=1 iff n is squarefree) that you can not
find in any book despite it has very interesting properties.

Keep thinking!