Wikipedia:Reference desk/Archives/Mathematics/2010 November 27

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 27

Composite Number Factorization Equation

As some Wiki users' suggestion, I put this question here.

$a\in Z^{+}$ and is sufficiently large, thus its factors satisfy the following equation. Namely $a$'s factors in $(1,a)$ can be found by solving the following equation:

$\sin ^{2}({\frac {{a}\pi }{x}})+\sin ^{2}(\pi x)=0$.

Proof

It requires that both ${\frac {a}{x}}$ and $x$ be integer. Thus $x$ is a factor of ${a}$.

Questions: 1. Is this proposition correct? 2. If so, can we find a closed-form solution, if I don't mistake the term "closed-form solution"? 3. If so, is there a computational way O(log a) ?

This is an entangling question to me for weeks. But I have to leave it to the real mathematical people whose career is on this. —Preceding unsigned comment added by Symbolsequence (talk • contribs) 16:44, 27 November 2010 (UTC)

Let me quickly answer your questions as yes, no, and no. Hopefully someone else has time to elaborate further (and double-check if I'm right). See also Integer_factorization#Difficulty_and_complexity. Eric. 82.139.80.250 (talk) 17:19, 27 November 2010 (UTC)

(1) Yes. In general, A^2 + B^2 = 0 if and only if A=B=0 for A and B real, which is a consequence of A^2 = 0 if and only if A=0 in the reals. The rest is simpler. (2) I very much doubt you could find any useful closed form solution. For instance, I asked Wolfram Alpha to solve the equation for x and it wasn't able to. (3) Likely certainly not, using just that formula. Suppose you were able to get a list of the roots of that equation, somehow--this is nontrivial, but say it was possible. You'd have not only all prime factors, but all factors in general. You'd also need a way to determine multiplicities from a list of roots. 67.158.43.41 (talk) 18:50, 27 November 2010 (UTC)

For a = n# (n primorial) the number of prime factors is n (taking n prime for convenience) and any subset of those prime factors determines a unique factor of a. There are 2^n subsets, so 2^n factors. There are about n digits in n# since ln(n#) ~ n. Thus the list of factors to sift through is exponential in the number of digits of a, and not linear like you wanted (or polynomial like I suspect you meant to want). 67.158.43.41 (talk) 19:34, 27 November 2010 (UTC)

This is not quite true, as actually log(n#) ~ n log n, thus a has $(2+o(1))^{\frac {\log a}{\log \log a}}$ divisors. (This bound is optimal, every number has at most that many divisors.) This does not make fundamental difference for your purposes, but let's keep the facts straight.—Emil J. 18:26, 29 November 2010 (UTC)

It is better to think of this approach as looking for simultaneous solutions of $\sin(a\pi /x)=0$ and $\sin(\pi x)=0$. Summing the squares only conceals this, at the expense of introducing a singularity along the solution set (which rules out many numerical methods like Newton's method). This leaves the question of whether there are efficient algorithms for finding approximate solutions to overdetermined systems of general transcendental equations. The answer clearly should be "no", but I wouldn't know how to go about proving the result (or even formulating it in a precise enough way that would make the proof possible). Sławomir Biały (talk) 20:48, 27 November 2010 (UTC)

I don't think this is going anywhere. If you rewrite this slightly as $\sin(2\pi a/x)=0$ and $\sin(2\pi x)=0$ (assume $a$ odd), or again slightly differently as $\cos(2\pi a/x)\cdot \cos(2\pi x)=1$, this comes down to $e^{2\pi i(a/x+x)}=1$ or searching for an integer $x$ such that $a/x+x$ is also an integer, which again comes down to finding a perfect square of the form $k^{2}-a$ as described in square number. Nageh (talk) 23:04, 27 November 2010 (UTC)

If you take that line of reasoning far enough you get Fermat's factorization method. CRGreathouse (t | c) 16:12, 29 November 2010 (UTC)

Good point! Nageh (talk) 19:00, 29 November 2010 (UTC)

I have not touched complex analysis for many years. Many years ago, it was just a undergraduate course. But I think x should be treated as a complex number. That is total out of my area. I personally at least tried a Taylor expansion, a complex equation,a dozen of a4 papers. While thanks for all the replies. Symbolsequence

I assume when you say "complex number" you actually mean Z[i] (Gaussian integer) rather than C (complex number). CRGreathouse (t | c) 06:11, 1 December 2010 (UTC)

To solve the roots of a polynomial, suppose the Taylor expansion converges, there will be C (complex number) roots. So there will be two other questions. Will Taylor expansion work, say expanding from sqrt a ? The polynomial is numerically solvable with QR method. Is there any relation between the complex roots and the polynomial's turning points? Symbolsequence

do all simply complete sets of equations have a total matrix?

I know you can set up a total matrix for most simply complete sets of equations (trivially) but is there a proof that all simply complete sets of equations would have a total matrix? Maybe it's obvious that they must, but if so I'm missing it. 62.54.13.205 (talk) 22:59, 27 November 2010 (UTC)

Can you explain your terminology? I couldn't find Wikipedia articles for the terms you mention. -- Meni Rosenfeld (talk) 14:37, 28 November 2010 (UTC)

I don't know the answer to his question, but a set of equations can be simply or fully complete, depending on the depth of completeness (i.e. whether all segments connecting them are real (non-imaginary), and then whether the segments connecting those segments are themselves all non-imaginary. There is no third degree, because if the equations are fully complete, they are complete to any "depth"). The total matrix is simply the n-dimensional matrix consisting of the same information in vector form, and as I said it only makes sense for n to be 2 or 3 (depending on whether you are talking about the total matrix of a simply or fully complete set of equations). You can calculate further dimensions just given the 2- or 3-dimensional matrix respectively. That's what the terminology means, but I do not know of a proof that a simply complete sets of equations would have to have a total matrix. I've never seen one that wouldn't have one, though... 84.153.230.216 (talk) 20:52, 28 November 2010 (UTC)

I'm afraid that doesn't really clear things up much. What exactly are "segments connecting equations"? --Trovatore (talk) 21:50, 28 November 2010 (UTC)

You must to graph the equations and to connect the tangents of it. 80.14.156.245 (talk) 15:54, 29 November 2010 (UTC)

An example would help. -- Meni Rosenfeld (talk) 16:46, 29 November 2010 (UTC)