Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a number $x = p_1^{e_1}\cdots p_n^{e_n}$ with different primes $p_i$ and exponents $e_i \ge 1$, is there an efficient way to find $p_1\cdots p_n$?

I ask this because for polynomials it's easy: with $K$ a field of characteristic $0$ and $$f = g_1^{e_1} \cdots g_n^{e_n} \in K[X]$$ irreducible we have $$g_1 \cdots g_n = \frac{f}{\mathrm{gcd}(f,f\,')}$$ where $f\,'$ is the formal derivative.

This proof can't be used for integers, unless there's a trick that I don't see.

share|improve this question
1  
I think it will work with the arithmetic derivative in place of the formal derivative, but then efficient computation is another story. –  anon Jul 16 '12 at 16:11
    
@anon Oh this is interesting, I haven't seen that. You're right, it is much more difficult to compute, since it doesn't satisfy a nice rule for sums. –  Dog Jul 16 '12 at 16:16

1 Answer 1

up vote 6 down vote accepted

Currently, no feasible (polynomial time) algorithm is known for recognizing squarefree integers or for computing the squarefree part of an integer. In fact it may be the case that this problem is no easier than the general problem of integer factorization.

Computing the radical $\rm\:rad(n)\:$ is equivalent to computing the squarefree part $\rm\:sf(n)\:$ because

$$\rm rad(n)\, =\, sf(n)\, sf(n/rad(n)) $$

This problem is important because one of the main tasks of computational algebraic number theory reduces to it (in deterministic polynomial time). Namely the problem of computing the ring of integers of an algebraic number field depends upon the square-free decomposition of a polynomial discriminant when computing an integral basis, e.g. [2] S.7.3 p.429 or [1] This is due to Chistov [0]. See also Problems 7,8, p.9 in [3], which lists 36 open problems in number theoretic complexity.

The primary reason that such problems are simpler in function fields versus number fields is due to the availability of derivatives. This opens up a powerful toolbox that is not available in the number field case. For example once derivatives are available so are Wronskians - which provide powerful measures of dependence in transcendence theory and diophantine approximation. A simple yet stunning example is the elementary proof of the polynomial case of Mason's ABC theorem, which yields as a very special case a high-school-level proof of FLT for polynomials, cf. my MO post and my old sci.math post [4].

Such observations have motivated searches for "arithmetic analogues of derivations". For example, see Buium's paper by that name in Jnl. Algebra, 198, 1997, 290-99, and see his book Arithmetic differential equations.

[0] A. L. Chistov. The complexity of constructing the ring of integers
of a global field. Dokl. Akad. Nauk. SSSR, 306:1063--1067, 1989.
English Translation: Soviet Math. Dokl., 39:597--600, 1989. 90g:11170
http://citeseerx.ist.psu.edu/showciting?cid=854849

[1] Lenstra, H. W., Jr. Algorithms in algebraic number theory.
Bull. Amer. Math. Soc. (N.S.) 26 (1992), no. 2, 211--244. 93g:11131
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.8382

[2] Pohst, M.; Zassenhaus, H. Algorithmic algebraic number theory.
Cambridge University Press, Cambridge, 1997.

[3] Adleman, Leonard M.; McCurley, Kevin S.
Open problems in number-theoretic complexity. II.
Algorithmic number theory (Ithaca, NY, 1994), 291--322,
Lecture Notes in Comput. Sci., 877, Springer, Berlin, 1994. 95m:11142
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.4877

[4] Dubuque, Bill. $ $ sci.math.research post, 1996/07/17
poly FLT, abc theorem, Wronskian formalism [was: Entire solutions of f^2+g^2=1]
http://groups.google.com/group/sci.math/msg/4a53c1e94f1705ed
http://groups.google.com/groups?selm=WGD.96Jul17041312@berne.ai.mit.edu

share|improve this answer
    
Here is a link to that page in Pohst-Zassenhaus. –  J. M. Jul 16 '12 at 16:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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