Ghost-Witt sequences vs. ghost-Polya-Burnside sequences? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T20:03:39Z http://mathoverflow.net/feeds/question/16978 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/16978/ghost-witt-sequences-vs-ghost-polya-burnside-sequences Ghost-Witt sequences vs. ghost-Polya-Burnside sequences? darij grinberg 2010-03-03T16:31:54Z 2012-03-11T19:40:20Z <p><strong>If you're in a hurry scroll down until the questions:</strong></p> <p>First the known part:</p> <p>A sequence $\left(b_1,b_2,b_3,...\right)$ of integers will be called a <em>ghost-Witt sequence</em> if there exists a sequence $\left(x_1,x_2,x_3,...\right)$ of integers such that $\left(b_n=\sum\limits_{d\mid n}dx_d^{n/d}\text{ for every positive integer }n\right)$. (The reason for this naming lies in the big/universal Witt polynomials, of course.)</p> <p>There exist several equivalent criteria for when a sequence $\left(b_1,b_2,b_3,...\right)$ of integers is a ghost-Witt sequence. One of them is that $b_{n/p}\equiv b_n\mod p^{v_p\left(n\right)}$ for any positive integer $n$ and any prime divisor $p$ of $n$, where $v_p\left(n\right)$ denotes the $p$-adic valuation of $n$. Another is that $n\mid \sum\limits_{d\mid n}\phi\left(d\right)b_{n/d}$ for every positive integer $n$, where $\phi$ is the Euler totient function. There are more (I listed some of them in <a href="http://mit.edu/~darij/www/algebra/witt5.pdf" rel="nofollow">Witt#5</a> Theorem 15), but there are yet more - I plan to write them up yet.</p> <p>This can be generalized several times; besides, the above criteria (well, some of them) easily show that the sum and the product of two ghost-Witt sequences are ghost-Witt sequences again (which leads to the integrality of big/universal Witt polynomials, but only if one generalizes this properly to polynomials instead of integers; otherwise you just get that the big Witt polynomials are integral-valued, but this doesn't mean that their coefficients are integers).</p> <p>Enough ramblings - here is what I am wondering about:</p> <p><strong>Questions:</strong></p> <p>A sequence $\left(b_1,b_2,b_3,...\right)$ of integers will be called a <em>ghost-Burnside sequence</em> if $\left(n\mid \sum\limits_{d\mid n}\phi\left(d\right)b_d^{n/d}\text{ for every positive integer }n\right)$.</p> <ul> <li>Is the sum / the product of two ghost-Burnside sequences another ghost-Burnside sequence?</li> <li>Are there any nice equivalent criteria? In particular, is there a criterion similar to the definition of a ghost-Witt sequence?</li> </ul> <p>Why do I care? Because the polynomial $\frac{1}{n}\sum\limits_{d\mid n}\phi\left(d\right)X_d^{n/d}$ is the cycle index of the cyclic group $\mathbb Z / n\mathbb Z$. It is not an integer polynomial, and not even an integer-valued polynomial, but one of the results of Polya enumeration theory states that $\frac{1}{n}\sum\limits_{d\mid n}\phi\left(d\right)\left(Y_1^d+Y_2^d+...+Y_k^d\right)^{n/d}\in\mathbb Z\left[Y_1,Y_2,...,Y_k\right]$ for any $k\geq 0$ (actually, this can be shown using Theorem 13 in <a href="http://mit.edu/~darij/www/algebra/witt5.pdf" rel="nofollow">Witt#5</a> as well). This makes every sequence of the form</p> <p>$\left(u_1^d+u_2^d+...+u_k^d\right)_{d\text{ positive integer}}$</p> <p>for integers $u_1$, $u_2$, ..., $u_k$ a ghost-Burnside sequence. I hope for a kind of converse; of course, it will require considering finite sequences only and possibly only up to congruence modulo $n$. EDIT: Sorry, this approach is doomed to fail. All the sequences constructed this way are not only ghost-Burnside, but also ghost-Witt, and we can't get the remaining ghost-Burnside sequences. (Yes, being ghost-Witt is stronger than being ghost-Burnside; but I don't have a nice proof.)</p> <p><strong>Results so far:</strong> If we let $m$ be a positive integer and require $n\mid \sum\limits_{d\mid n}\phi\left(d\right)b_d^{n/d}$ to hold for $n\mid m$ only (and not necessarily for all positive integers $n$), then I can prove that the sum and the product of two ghost-Burnside sequences are ghost-Burnside sequences again, if $m$ is a prime power or a squarefree integer. I think I also did it for the case $m=p^2q$, which already required some casebash. The other cases are scaring me off...</p> <p>I am recording the results for myself:</p> <p>(1) If $m=p^k$ is a power of a prime $k$, then a sequence $\left(b_1,b_2,b_3,...\right)$ of integers (of course, only the $b_{p^i}$ members matter) is ghost-Burnside if and only if $b_{p^u}\equiv b_{p^{u+1}}\mod p$ for every $0\leq u\leq k-1$. No typo here: it's $\mod p$, not $\mod p^u$ as in the ghost-Witt case!</p> <p>(2) If $m=pq$ is the product of two distinct primes $p$ and $q$, then a sequence $\left(b_1,b_2,b_3,...\right)$ of integers (of course, it's all in the terms $b_1$, $b_p$, $b_q$, $b_{pq}$) is ghost-Burnside if and only if</p> <p>$b_1\equiv b_p\mod p$; $b_1\equiv b_q\mod q$; ($b_q\equiv b_{pq}\mod p$ OR $p\mid q-1$); ($b_p\equiv b_{pq}\mod q$ OR $q\mid p-1$).</p> <p>(3) If $m=p^2q$ for two distinct primes $p$ and $q$, then a sequence $\left(b_1,b_2,b_3,...\right)$ of integers (this times six terms matter) is ghost-Burnside if and only if</p> <p>$b_1\equiv b_p\equiv b_{p^2}\mod p$; $b_1\equiv b_q\mod q$; ($b_q\equiv b_{pq}\mod p$ OR $p\mid q-1$); ($b_p\equiv b_{pq}\mod q$ OR $q\mid p-1$); ($b_{p^2}\equiv b_{p^2q}\mod q$ OR $q\mid p-1$); [($b_{pq}\equiv b_{p^2q}\mod p$ AND $p\not\mid q-1$) OR ($b_q\equiv b_{pq}\mod p$ AND $p\mid q-1$) OR ($p^2\mid q-1$)].</p> <p>(4) Generalizing (2): If $m$ is the product of finitely many distinct primes (i. e. if $m$ is squarefree), then a sequence $\left(b_1,b_2,b_3,...\right)$ of integers is ghost-Burnside if and only if</p> <p>($\phi\left(d\right)b_d\equiv \phi\left(d\right)b_{pd}\mod p$ for every $d\mid m$ and every prime $p$ such that $pd\mid m$).</p> <p><strong>Dreams:</strong></p> <p>If this works, we could move on to groups more interesting than cyclic groups.</p>