Wikipedia:Reference desk/Archives/Mathematics/2013 April 17

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

April 17

Quadratic Frobenius test

In this paper, the authors describe a primality test they developed. Some of the notation in the paper is confusing to me. In particular:

• on p.33 in the definition: What does (b² + 4c | n) = –1 mean? Is the expression inside the parentheses a quotient?
• on p.34, in the expression $x^{n+1}\,{\bmod {\,}}{\big (}n,x^{2}-bx-c)$, what does the comma inside the parentheses mean? They say "the tests involve computations in the ring $\mathbb {Z} \left[x\right]{\big /}\left(n,f(x)\right)$, where $f(x)\in \mathbb {Z} \left[x\right]$ and n is an odd positive integer" and that they will be considering the case $f(x)=x^{2}-bx-c$. Could someone explain this in simple terms?

Thanks for any light you can shed on this. -- Toshio Yamaguchi 17:12, 17 April 2013 (UTC)

The notation (x | n) is the Jacobi symbol. If n is prime, this is just the Legendre symbol, which is 1 if x is a square modulo n, and -1 otherwise (except it's 0 if x is divisible by n). Otherwise there's a formula for it as explained on the Wikipedia page for the Jacobi symbol.

The modulo (n, f(x)) means that they are working in a univariate polynomial ring modulo the ideal generated by n and f(x). This just means that they are considering polynomials in one variable x with coefficients integers mod n, and saying two such polynomials are equivalent if their difference is divisible by f(x). In particular, the polynomial f(x) is equivalent to the 0 polynomial. As an example, if f(x) = x, then this ring reduces to the integers modulo n.

I hope that's understandable! -- Sam^Talk 19:32, 17 April 2013 (UTC)

Okay, thanks. I think I will have to study this a bit more in order to fully digest it, but now at least I know what the notation means. -- Toshio Yamaguchi 08:48, 18 April 2013 (UTC)

Infinitesimal

Is it possible to prove that there exist an infinitesimal, without using theorems based on the assumption that it does. Plasmic Physics (talk) 23:30, 17 April 2013 (UTC)

Does Non-Archimedean ordered field answer your question? If not, what is your question? Sławomir Biały (talk) 23:46, 17 April 2013 (UTC)

Try infinitesimal, which has lots of detail on how infinitesimals can be rigorously defined without creating any inconsistencies. For a rigorous treatment of infinitesimals in calculus, see non-standard analysis. Staecker (talk) 01:03, 18 April 2013 (UTC)

That's not entirely what I'm looking for. Those articles seem to indicate that infinitesimals exist, because the reasoning for it's existance requires it to exist. There seems to be circular reasoning: "If theorem A is true, then statement B is true. However, theorem A is only true if statement B is true." Unless, I've completely missed something, this seems like a classical tautology, and does not equate to proof. Plasmic Physics (talk) 02:29, 18 April 2013 (UTC)

Does the same critique hold for imaginary numbers or irrational numbers? Both concepts whose existence have been criticised in the past, hence their derogatory names. Mathematics can start with a set of axioms and work from there. So you can take an irrational numbers, imaginary numbers or infinitesimals as part of your axiomatic system. If we work with the rationals irrational numbers don't exist but working with the reals they do. In each case we extend one part of mathematics by adding new axioms. What is important is whether the new system is consistant. --Salix (talk): 06:33, 18 April 2013 (UTC)

Not, quite. i is essenally, a placeholder for an incalculable function of a real number. An irrational number is an irreducable function of a real number. Both concepts are consquences of axioms. An infinitesimal appears to be an unjustified axiom in itself, therefore, it is what it is, and not because of reason. Plasmic Physics (talk) 07:31, 18 April 2013 (UTC)

In set theory, there is the axiom of infinity, which arises because the other axioms don't define an infinite set. This suggests that an infinitesimal quantity might be on the same footing, since it is kind of the "dual" of infinity, but I am just guessing. The implication for me is that an infinitesimal can't be defined without an axiom designed for either infinity or the infinitesimal itself, but like I say, just a guess. IBE (talk) 07:13, 18 April 2013 (UTC)

Adding to that, the specific part of the article you want is the section titled "Independence", which discusses the need for the axiom in set theory (I would link the specific section, but somehow I can't get the within-page link to work). IBE (talk) 07:19, 18 April 2013 (UTC)

(edit conflict)According to my reasoning, zero ought to be the dual of infinity. Zero represents an empty set, and infinity represents a full set, both lead to complications of certain functions. Plasmic Physics (talk) 07:31, 18 April 2013 (UTC)

The page on infinitesimal gives several constructions that contain them, the field of Laurent Series with a finite number of negative terms contains them; I don't think the existence of this field is anymore contentious than that of the p-adic fields (which aren't contentious at all). So I'm not sure what you're looking for. It's almost like asking for a vector space that doesn't assume it has vectors; infinitesimals can be defined as any blah blah that satisfy blah blah blah, then you look for spaces that contain them. Again, with vector spaces, for any object satisfying the axioms, it makes sense to call the elements vectors, outside of this, there is no thing that is a vector.Phoenixia1177 (talk) 08:07, 18 April 2013 (UTC)

As for the set theory stuff, you don't need any extra axioms to get the constructs listed. As for 0 causing problems for functions, there is just a big a problem with any number: 1/x has a problem at 0, 1/(x-1) has the same issue at 1, 0 is not special in this regard. Infinity, on the other hand, as a real number (or such) is not defined and causes no problems, limits are a different thing from this. Finally, you can use ordinals/cardinals for "infinite numbers", but this is a whole different subject and entirely unrelated to infinitesimal. Sorry if any of my tone comes off as rude, I had to write this quickly.Phoenixia1177 (talk) 08:06, 18 April 2013 (UTC)

I guess, what I'm trying to get at, is why can I not perform functions on infinity? I'm not statisfied with, "because John Doe said so." That seems to be the only obstacle for an infinitesimal equating to zero. I'll just have to invent a new number, greater than all numbers, that does allow me to do just that. That doesn't require me to settle for limits, as an answer to functions on it. Plasmic Physics (talk) 08:41, 18 April 2013 (UTC)

That's kind of like asking why you can't have a number that squares to -1 when working in the reals. It's how the reals are defined, if you don't like it, define something else and work with that. Anything you work with is just a set equipped with some other sets (essentially), so the reals aren't anymore special than anything else; they are special to us humans, so if what you come up with is a contrived and artificial extension, nobody might care, but there's nothing forbidding you from doing this. On that subject, that's exactly what the field of laurent series is, a structure with infinitesimals, you might as well just do stuff with this if you want (it's no more, or less, existing than the reals themselves.). As for defining functions at infinity, a lot of people have done this a lot of ways, there's nothing to say you can't; but you can't do it and still be in the real numbers, and if you do it, you can't get contradictions. Just because we use the reals, which have certain limitations, only means that people care more about results in them and that they're more generally accessible than other systems; it's the same reason the reals are the most common completion of the rationals, even though you could easily teach a highschooler, to the same level, about p-adics.Phoenixia1177 (talk) 08:57, 18 April 2013 (UTC)

"I'll just have to invent a new number, greater than all numbers ..." - that's your fatal flaw here, Plasmic Physics. Any number you can possibly "invent" that is subject to mathematical operations is well, just another number. Try adding 1 to it. There goes your "greater than all numbers" theory. As has been pointed out here before, infinity is not a number. It is more like a philosophical concept. Try calculating the square root of "beauty", or the logarithm to base 10 of "consciousness". -- Jack of Oz ^[Talk] 09:53, 18 April 2013 (UTC)

Jack, the phrase infinity is not a number is often heard, but it has basically no content. Certainly, infinity is not a natural number or a real number or a complex number. But there is no general concept of "number" to exclude infinity from.

There are certainly infinite cardinal numbers and infinite ordinal numbers. The smallest infinite cardinal number is aleph naught (written $\aleph _{0}$). Your challenge to add 1 to it is easily answered; what you get is again aleph naught.

The smallest infinite ordinal number is ω. If you add one to it on the right, you get ω+1.

Now, admittedly, you wouldn't call either of these just-plain-"infinity" full stop, because they're more specific than that. But see also extended real number and extended complex number for structures that do have an element called "infinity", and where it is described with the word "number". --Trovatore (talk) 02:42, 19 April 2013 (UTC)

Tersely: Let F be the set of maps naturals -> naturals; let G: F -> naturals; then define an extension f* of f (in F) to naturals + {infinity), f*(infinity) = G(f). Of course, this won't do anything like you want in almost every case, so extensions abound. If you want to be more specific, just say infinity is larger than the rest, then do whatever you want to extend functions; properties might not be conserved, but it's still larger. It goes on. As long as your axioms don't contradict, you'll have models.Phoenixia1177 (talk) 10:12, 18 April 2013 (UTC)

This new number would not be a number 'per se', but more like a place-holder, as i is a place holder for the square root of a negative number. I'll call this place-holder 'inverse-zero' represented by '0^-1' or '1/0'. I'll assign the property to it that that 0^-1 is greater, equal to, and less than itself, thus all numbers, except negative -0^-1, added to it equals itself. In addition to that, 0^-1 is either even or odd, or both, or neither, but not all at once. Plasmic Physics (talk) 10:43, 18 April 2013 (UTC)

Post Script: I can't calculate the square-root of "beauty", but I can double a "half-wit" - it yields one "twit." Plasmic Physics (talk) 10:51, 18 April 2013 (UTC)

Even means 2 divides it, odd that it doesn't; there is no time framework in place for it to change and it can't be both. It can't be neither either; 2 divides it, or not. At any rate, if you sort out the basic logical issues, as mentioned, you'll find that once this works, it doesn't have much to say; and a lot of words we use for properties now either don't work right, or need to be made very artificial. In short, if you get it working, it's not going to give you anything neat that you don't have before; but it will complicate everything you want it to be. "i" is not "just a placeholder" any more than "1" or "736" is, so I don't follow that- by the way, adding "i" gets you something powerful, the complex numbers, because it's a powerful concept with many deep connections; what you proposed doesn't seem to have said properties. Again, though, what is your objection to the big list at infinitesimal article? Phoenixia1177 (talk) 10:53, 18 April 2013 (UTC)

Perhaps then, not 'neither'. Not 'time' framework, but 'conditional' frame work. (Let 0^-1 be even, f(x) = ...) Since 0^-1 is equal to all number added to itself, it can be both odd and even, or either. I should also mention that it can be both, or either irrational or rational. Well, once I get this working, I can get rid of the infinitesimal 'i' is a placeholder for (-1)^½, in that it is equivalent to it, just like 'y' is the placeholder for f(x); 1 is not a place-holder, because 1 is not a function, 1 is equal to 1. A placeholder is a symbol used to represent a particular function that cannot be calculated. Plasmic Physics (talk) 11:18, 18 April 2013 (UTC)

By my own reasoning 0^-1 would not be the placeholder, but the function represented by a hypothetical placeholder. I have an idea for an actual placeholder: a horizontally bisected zero with each half translated to the other's position, forming structure similiar in appearance to a curved 'H', and call it 'orez'. Plasmic Physics (talk) 11:38, 18 April 2013 (UTC)

You will not get this working or it won't be worth getting it working. As it stands now, rational means "is in the rational numbers", it is either in the set or not; same for even. You can redefine these words, but that's, essentially, going to be a waste of time; it's like redefining prime to include 1 or computable to include the function that solves the halting problem; you haven't said anything new about the original concepts and the new ones don't work the way the old one's did. Your placeholder discussion doesn't make sense, I could write "|", ")" or "lenfwejlk2432ty" for "1" if I want, that's no different with i, or anything else; if you mean more than this, I'm not sure what you're saying because I don't think it's standard terminology. Anyways, I wish you the best of luck:-)Phoenixia1177 (talk) 02:30, 19 April 2013 (UTC)

You're missing the property that I've defined for orez, which is H ⋚ H, thus (H + π = H) → (H E Q), and (H + 3/7 = H) → (H E Q), thus H is either an element of Q or not. I'm not redefining operations, I'm applying opperations to a newly defined placeholder/number. I'll keep working on this new number on my own. Plasmic Physics (talk) 03:35, 19 April 2013 (UTC)

Have fun:-) I think we may be using some words differently, so I'm not really sure what you're saying above.Phoenixia1177 (talk) 03:38, 19 April 2013 (UTC)

It is more that one needs axioms to say they don't exist rather than ones to say they do. I guess it really depends on what you mean by exist but in maths one normally accepts anything that is consistent with one's axioms as 'existing' though others think of axioms as never being complete enough to really pin down some essence of existence and of us needing more and more of them. Dmcq (talk) 09:58, 18 April 2013 (UTC)

I think the issue is that you are always going to get nonstandard models with first order logic, people don't like talking about all of these when they say "exists", they want something unique because they have that singular thing in mind, not some fragment of it that the axioms allow them to discuss. My two cents, different shades for different folks; I like knowing that there's something I haven't said yet and will never say enough to nail it down.Phoenixia1177 (talk) 10:12, 18 April 2013 (UTC)

For a model of a number continuum that includes both infinite and infinitesimal numbers without explicitly introducing them in its axioms, see surreal number. Gandalf61 (talk) 11:04, 18 April 2013 (UTC)

Thing is, mathematicians are themselves physical systems subject to the known laws of physics. So, if mathematicians invent something and use it, what they are doing is also describable by ordinary quantum mechanics. Count Iblis (talk) 12:47, 18 April 2013 (UTC)