6
$\begingroup$

While watching a video of someone playing the video game Beyond: two souls, I saw the next formula $$N_k=\frac{1}{k}\sum_{d|k}\mu(d)n^{k/d}\text{,}$$ which clearly is a reference to number theory since it is a convolution of the Möbius function and the arithmetic function $x\mapsto n^x$ divided by other arithmetic function.

I have tried to search some identity of this form in my references of arithmetic functions unsuccessfully, so does this formula has any actual appearance (in the sense of meaning beyond being a weird convolution) in number theory? Or has it been a creative way of referencing mathematics -and in particular, number theory-?

$\endgroup$
2
  • 1
    $\begingroup$ Where does the formula appear in the video? $\endgroup$ Jan 29, 2014 at 23:19
  • 1
    $\begingroup$ @DanielMcLaury Between 24:54 and 25:15, the scene of the written exam. (Apparently, depending of the computer the link does not send exactly to the point of the video it points.) $\endgroup$ Jan 30, 2014 at 17:10

2 Answers 2

7
$\begingroup$

If $n$ is a power of a prime, then this counts irreducible polynomials over the finite field of corresponding prime-power cardinality, as user72870 points out.

If $n$ is not a power of a prime, then you have to resort to counting something else instead, namely necklaces (warning: $k$ and $n$ are switched in the Wikipedia formula).

Interestingly, without a combinatorial interpretation, it's not at all clear that this function produces integers!

$\endgroup$
1
5
$\begingroup$

It is the number of monic irreducible polynomials of a given degree over a finite field. See here.

$\endgroup$
2
  • $\begingroup$ You are right, I totally forgot that formula. :) $\endgroup$ Jan 29, 2014 at 22:54
  • $\begingroup$ This is true only if $n$ is a power of a prime $\endgroup$ Jan 29, 2014 at 22:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .