@EmilJeřábek True that. I think the OP is asking what the best method is, and whether the complexity is a particular one. But maybe I misunderstood your comment: are randomized polynomial factoring algorithms, that take $poly(\ell log(p))$ time, the best known? With no dependence on $\ell$?

Polynomial time polynomial factoring gives polynomial time in $\ell$ - not in $log(\ell)$ - which is not polynomial time in the input length.

Where can one read on the hinted equivalence of the two problems? Are they polynomialy reducible to each other?

Say, how many formal groups are there, and how many such towers are there? The formal groups will be determined by their logarithm, each of which is a countable number of coefficients, each of which in turn can be approximated by an integer while preserving the field extension tower (I think). As for the number of towers, I've heard the words "wild problem" before. Is it possible that once you allow $\zeta_p\in k$, then there are more than a countable number of towers? Since everything is abelian, maybe it's not possible...

After choosing the standard branch for log (which will cause no problem since p is odd), and taking derivatives, this question reduces to one about equal sums of powers, specifically the maximal k s.t. $\sum a_i^k=\sum b_i^k$ where $x_i=exp(2\pi \sqrt{-1} a_i/p)$, $a_i\in[-p/2,p/2]$, and similarly for $b_i$.

Similar to my comments at mathoverflow.net/questions/70024/…, given the parity conjecture for elliptic curves and the results in Levirance '95 (and some congruence work), there exists a rational solution to each of the representations in the question. But I doubt this direction can say anything about integral solutions.

Do you have a reference on hand that $t<2p$?

Hi! Does this problem have a name?

There are multiple math.stackexchange questions on this question (full rank in quotient ring implies full rank). Milne's notes on algebraic number theory are classic by now, though they might involve more than you need.

This all comes down to the determinant being non-zero, which is equivalent to full rank. Since all the entries of the matrix are in the ring of cyclotomic integers $\mathbb{Z}[\omega]$ of the cyclotomic field $\mathbb{Q}[\omega]$, so is the determinant. Then we can go modulo $p$. A cyclotomic integer that is not zero modulo $p$ must itself be nonzero. Hence, if the reduction is of full rank, then the reduction of the determinant is nonzero, and then the determinant itself must be nonzero, and thus the original matrix has full rank no matter the ring (cyclotomic integers or complex). There are

Given the last equality stated, it seems beneficial to work over $\mathbb{Z}[\omega]/(p)$. You have: $$A^p\equiv \sum (T^lW^l)^p\equiv\sum det(W^l)I.$$ p-th roots of unity have only one linear relation. If you don't fall on it, this proves $A$ has full rank over the cyclotomic ring, and hence also over complex numbers.

An anthropic prinicple argument for mathematics?

why off topic?? this is a pretty hard question well in the research interests of many people here.

@Edgar: nice! btw, I think the $(2\pi)^{12}$ factor can be removed.

Considering only congruence groups, I think there are only a finite number of them with a hauptmodul, so also only a finite number of $k=1$ cases to check, and since hauptmodul is unique up to mobius transformations, really only a finite number of differential equations to check. As for large k, I would be interested to know an answer for $\Delta(1/j)$.