Wikipedia:Reference desk/Archives/Mathematics/2009 December 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.

December 27

Algorithm to reduce polynary equations to minimum form

I asked this before and maybe the question was ignored due to the holidays...

Is there an algorithm (like for the simplex method in linear programming) to reduce polynary equations to minimum form? 71.100.6.153 (talk) 02:06, 27 December 2009 (UTC)

I believe that the problem is your use of "polynary". That is not a well-defined word. The meaning depends on which group of people is using it. If you just made it up, please define what you mean by it. Otherwise, define what the group of people you got it from intend for it to mean. It literally means "pertaining to many" in the way that binary means "pertaining to two". So, it means "can have many values". Most equations can have many values. Most variables can have many values. Therefore, the usage is very important to make sense of the question. -- kainaw™ 03:04, 27 December 2009 (UTC)

My intended meaning of polynary is identical to the phrases "multiple state variable" or "many stated variable" or "poly-stated variable" in the same sense that binary pertains to two. My usage covers binary variables and any variable with discrete and finite number of states. My usage does not include fractions directly since probability values can be normalized to percentages and percentages are meaningless beyond a few decimal places which can be rounded or truncated to result in only integer values. 71.100.6.153 (talk) 15:44, 27 December 2009 (UTC)

A polynary equation is a logical equation with variables which may have two states although binary is the specific term used to refer to such an equation as trinary is the specific term used to refer to an equation of variables made up of three states. The algorithm I am looking for, however, should be applicable to all discrete and finite stated equations to include binary, trinary and beyond. 71.100.6.153 (talk) 00:11, 28 December 2009 (UTC)

In short, a polynary variable is any variable having a finite number of discrete states. 71.100.6.153 (talk) 00:20, 28 December 2009 (UTC)

In established terms polynary refers not to natural numbers but to a "...more recent notion..." of nominal numbers. (see Use of nominal numbers) 71.100.1.76 (talk) 19:25, 31 December 2009 (UTC)

Measure Theory & Countability

First of all, when I say that a set A is "bigger than" another set B, it means that B is entirely contained in A and that A and B are not equal. So B is a proper subset of A. Working an the interval [0,1] for example, I know that starting from a single point, we can work our way up to the Cantor set which is uncountable and still has measure zero. My question is what is the "biggest" subset of [0,1] that still has measure zero. All of [0,1] has measure 1 obviously.

I have the same question regarding countable sets (countable means finite or countably infinite) in [0,1] for example. Cantor showed (using his usual ingenious arguments) that starting from a single point, we can work our way up to the algebraic numbers which are countable. Is there any set "bigger" than the set of all algebraic numbers in [0,1] which is still countable? Thanks! -Looking for Wisdom and Insight! (talk) 02:56, 27 December 2009 (UTC)

Adding a single point (or any countable set) to a set which is countable/measure zero yields a new set which is again countable/measure zero. You'll need some better questions to get more interesting answers. Algebraist 03:07, 27 December 2009 (UTC)

I think that the OP is looking for the existence of a subset of [0,1] containing the algebraic numbers within [0,1], maximal with respect to the property that it is countable and has measure zero (you might as well omit the "measure zero" from the OP's question since any such countable set has measure zero). In this case, however, there is no such maximal set, for the reason given by algebraist (if M is any such countable set, $M\cup \{x\}$ for $x\in [0,1]\setminus M$ contains M and is countable, so M cannot be maximal with respect to the property of having measure zero). --PST 04:08, 27 December 2009 (UTC)

You know what I meant and I was afraid of this answer. I thought about that too but that is not what I was looking for. So what is the largest subset of [0,1] which is countable/has measure zero?-Looking for Wisdom and Insight! (talk) 03:37, 27 December 2009 (UTC)

There is no such countable set for the reason given by algebraist above. There is no such set having measure zero for exactly the same reason (if M is any such set having measure zero, $M\cup \{x\}$ for $x\in [0,1]\setminus M$ contains M and has measure zero, so M cannot be maximal with respect to the property of having measure zero). --PST 04:11, 27 December 2009 (UTC)

Basically, although many aspects of mathematics are firmed on intuition, which formalizm consolidates (and is thus often tacit), in this case formalizm is important to obtain some interesting intuition. --PST 04:14, 27 December 2009 (UTC)

The question is analogous to asking the existence of a "largest number"; unless you add extra assumptions to your definition of "number", you cannot obtain a meaningful answer. In this case, you will need to add additional assumptions to your definition of "set". --PST 04:17, 27 December 2009 (UTC)

Thanks for the explanation, everyone!-Looking for Wisdom and Insight! (talk) 04:29, 27 December 2009 (UTC)

Maybe more interesting answers can be found if we also consider description complexity. "Rational numbers" fails because a much bigger set (algebraics) can be obtained with an equivalently short description. "Algebraic numbers and $1/\pi$" fails because the added complexity of specifying $1/\pi$ is not justified by the increase of one element. In other words, that extra element does not "belong" in this set. So, is there a countable set which is significantly larger then algebraics and yet similarly simple? Is there some quantification of these notions, under which an optimal set can be found? -- Meni Rosenfeld (talk) 06:00, 27 December 2009 (UTC)

Perfect, like if all elements in a set share a common property. That is definitely a better wording of my question.-Looking for Wisdom and Insight! (talk) 07:02, 27 December 2009 (UTC)

The Computable numbers are countable and the only way you'll write a number that's not amongst them is by doing something like throwing a dice for each digit. Dmcq (talk) 22:55, 27 December 2009 (UTC)

Well, it depends on what you mean by the way, will I be man enough to ignore the barbarism a dice??? Probably not. At least I can rant about it in small text. by write such a number. Of course you can't really "write" it (because it would take too long) but you can certainly specify one, with no ambiguity whatsoever. For example, consider the number in binary representation that has a zero at position n if the Turing machine with Goedel number n halts, and a 1 otherwise. --Trovatore (talk) 23:01, 27 December 2009 (UTC)

The wikipedia article dice allows it for the singular form but yes die is better. A set larger than the algebraic numbers that includes practically everything before the 20th century can be got by using the hypergeometric series to generate extra numbers. Dmcq (talk) 23:12, 27 December 2009 (UTC)

We could extend that idea to the set of all numbers for which there exists a formula (in the first-order language of set theory) which your favourite set theory proves to uniquely define the number in question. That set's countable, and it contains every number you're ever likely to talk about. Algebraist 02:13, 28 December 2009 (UTC)

I'm not quite sure why you want to drag in provability. What exactly do you mean by saying that the theory proves that the formula describes "the number in question"? You can't talk about the number in question until you have a definition for it.

So presumably what you really mean is that the theory proves that the formula defines a unique real, and then consider the set of all reals that (Platonistically) satisfy some such formula. But then what does the proof add? Why not just consider the set of all reals that Platonistically are the unique real satisfying some formula, whether or not you can prove that there's a unique real satisfying the formula? --Trovatore (talk) 02:59, 28 December 2009 (UTC)

By the way have you come across the Vitali set? Dmcq (talk) 13:29, 29 December 2009 (UTC)

Largest countable this that and the other

This isn't exactly responsive to what the original poster asked, but it seems similar enough to mention. There are results from effective descriptive set theory that certain lightface pointclasses have largest countable members. For example there is a largest countable $\Pi _{1}^{0}$ set of reals. A set of reals is $\Pi _{1}^{0}$ if it's the complement of a $\Sigma _{1}^{0}$ set; a set is $\Sigma _{1}^{0}$ if it's the union of a collection of (open) intervals with rational endpoints, where some computer program, given infinite time, can list all the pairs of rational endpoints involved.

(So a $\Pi _{1}^{0}$ set is always closed, but being $\Pi _{1}^{0}$ is a stricter notion than being closed. The sense in which it is closed has to be somehow "effective" or "computable". For example there are uncountably many closed sets, but there are only countably many $\Pi _{1}^{0}$ sets, because there are only countably many computer programs.)

There's a classic paper by Donald A. Martin on this, in Proceedings of the Cabal Seminar, called Largest countable this that and the other.

I don't know how to characterize the largest countable $\Pi _{1}^{0}$ set, but the largest countable $\Sigma _{2}^{0}$ set is simply the set of all reals that are in Goedel's constructible universe. Obviously this requires something beyond ZFC; you have to be able to show that that set is countable. But I think the very modest assumption of zero-sharp suffices. I don't know whether you can prove in ZFC alone that there exists a largest countable set in any of these pointclasses. --Trovatore (talk) 23:14, 27 December 2009 (UTC)

Sorry, I had a total brain freeze. Actually most of what I write above is correct, except that I should be talking about the largest countable $\Pi _{1}^{1}$ and $\Sigma _{2}^{1}$ sets (note the superscript 1 instead of 0). The definition I gave for $\Pi _{1}^{0}$ is correct, but not relevant, because I should have been talking about $\Pi _{1}^{1}$ sets, which are much more complicated (as sets) and somewhat harder to explain in elementary terms. The largest countable $\Sigma _{2}^{1}$ set (not $\Sigma _{2}^{0}$) is the set of all reals in Goedel's constructible universe. --Trovatore (talk) 01:34, 28 December 2009 (UTC)

PST's response made me think of a (I hope) interesting question. Let X be the collection of all countable subsets of [0,1], partially ordered by set inclusion. Since there's no maximal element, by Zorn's lemma there exists a chain with no up bound. Can someone exhibit such a chain? I'm thinking about embedding all countable ordinals into [0,1] in some way... Money is tight (talk) 13:05, 29 December 2009 (UTC)

"In some way" — well put. Of course there is an injection from the set of all countable ordinals into [0,1]. If f is such an injection, then letting A_α be {f(β) | β < α}, then the A_α are your desired chain. Good example.

I don't know exactly what you're requiring when you say "exhibit" such a chain, though. It's consistent with ZF, without the axiom of choice, that no such f exists. In fact it follows from the axiom of determinacy, AD, that there is no such f. AD of course is inconsistent with the axiom of choice, or to put it another way, false.

In this context people tend to claim that there is no "explicit" such f. You see this claim all over the WP math articles when discussing objects whose existence can't be proved without AC. It's a problematic claim, as it tends to depend on what you mean by "explicit", which is a term that has no precise accepted definition. It may also depend on such things as whether V=HOD, which (unlike V=L) is not currently known to be ruled out by any accepted large cardinal hypotheses. --Trovatore (talk) 21:19, 29 December 2009 (UTC)

Math and calculations

I want to do math but I'm terrible with calculations. Is it possible to do math without calculating/solving complicated equations with formulas? If so, how? My friend's a math person and he says that when he does math he thinks and rarely does calculate. He says he researches algebra, but I thought algebra was about calculating??? He also says that math people don't do arithmetic with numbers. My world has collapsed! Help! Or maybe my friend's wrong. Can't calculators solve math? Why does he research it? What sorts of math are there (my friend says there's lots)? Please tell me how I can do math without my calculator! —Preceding unsigned comment added by 122.109.239.199 (talk) 09:54, 27 December 2009 (UTC)

See Mathematics. Some areas of mathematics (such as abstract algebra, as opposed to high-school algebra) don't involve arithmetic calculations at all. Some do, and application of these fields can benefit tremendously from the use of a calculator. Being comfortable around numbers and equations is an important skill for the mathematically literate. -- Meni Rosenfeld (talk) 11:49, 27 December 2009 (UTC)

So you should first learn how to do computations, and then you should learn how not to do computations. --pma (talk) 12:28, 27 December 2009 (UTC)

Good advice. --PST 12:44, 27 December 2009 (UTC)

"Your world has collapsed"? That should not be the case! Almost everyone is told that they are wrong about something, at some point in their lives; such is an important experience. With regards to computations, I have a couple of remarks. Firstly, I think that the mathematical brain, by default, has ability to do computations; that is, if you are able to do the "mathematics without computations", you should have the ability to do the "mathematics with computations". Basic computations really do not require extreme intelligence to carry out, save silly human errors. On the other hand, much of mathematics is not really concerned with computations; rather, it is concerned with deeper problems which may require computations (at some stage) to solve. In abstract algebra, for instance, one uses substructures to encapsulate computations abstractly (ideals in ring theory, subgroups in group theory, etc...). In another branch of mathematics, topology, much of the goal is to attain a strong intuition of closeness; although seemingly simple, this is very deep. Differential topology sometimes employs differential geometry for this purpose. Hope this answers your question(s). However, if this is an attempt to mock mathematics, please do not; mathematics has developed tremendously over the past few hundred years, and not surprisingly, it is difficult for many to comprehend the extent of this development (I should add that it was even difficult for me to comprehend during my first exposure to formal mathematics). --PST 12:43, 27 December 2009 (UTC)

Why do you want to do maths if you don't have some feel for what it is about? Being very good at calculating isn't that important though it is quite useful. I've known what maths is since I was a child stringing up a frame when I realized I didn't get a circle and I wondered how to arrange the pegs to get a circle. I can't see any basis for your desire to do maths. Dmcq (talk) 13:12, 27 December 2009 (UTC)

Skill with numbers is likely to develop with practice. The more you work with arithmetic and elementary algebra, the more proficient you will become. A solid basis in those areas is needed to progress to more advanced mathematics. Many of the branches of mathematics which do not work with computations are are too complex to be meaningful without the foundations. —Anonymous Dissident^Talk 13:29, 27 December 2009 (UTC)

I want to become a mathematician but I hate equations and formulas, and my friend says that's not necessary for mathematics. You tell me something, and probably that was what my friend said but I wasn't paying attention. Thanks! But why do people research mathematics? People research physics because it's important to know about the universe. People research medicine because it helps our survival. What's the use of mathematics without calculating??? I want to do math because my math teacher said to me when I was in high school that it's purpose is to shape the world, and that mathematicians are society's core, because of their mind boggling human-calculator ability. And if math's not about numbers, what is it about? My high school teacher said that math is about understanding different properties about numbers, such as prime and composite and he has a math degree. Many thanks for the responses. Please tell me why people think math though! It hurts my brain and isn't fun. But I need it to be part of society's finest. —Preceding unsigned comment added by 122.109.239.199 (talk) 13:48, 27 December 2009 (UTC)

You want to become a mathematician but you hate some aspects of it; it hurts your brain and isn't fun. Have you considered a career in masochism?→→86.160.104.185 (talk) 16:15, 27 December 2009 (UTC)

Please don't be disrespectful to the OP; he or she doesn't understand what mathematics is about and would like to better understand it, I'm sure you can provide some insight that would be useful to him or her. Eric. 131.215.159.171 (talk) 21:59, 27 December 2009 (UTC)

By now it should be considered very unlikely that the OP is asking these questions in good faith. 86's response is appropriate. -- Meni Rosenfeld (talk) 10:32, 28 December 2009 (UTC)

Considering the OP's more recent questions, you are probably right. However there is still no use to mocking him or her. Eric. 131.215.159.171 (talk) 01:40, 29 December 2009 (UTC)

It's possible you will find Lockhart's Lament interesting; it's an article about the teaching of high school mathematics in the US. Although it does not spend much time explaining what mathematics is, it does address some misconceptions of mathematics and explains what mathematics is not. Eric. 131.215.159.171 (talk) 22:05, 27 December 2009 (UTC)

The best way to judge whether you can become a mathematician is probably to simply find out if more time spent with it still leaves you feeling dislike toward it. In the meantime, you will become at least good enough at math to make a living doing something with math that doesn't involve actually being a mathematician. This just seems like a reasonable piece of advice/opinion for the OP. One thing about mathematics that is appealing and repellent at the same time is that it involves abstract objects directly and entirely, and its only connection to the 'real world' is through the filter of modelling. Doing mathematics per se involves ignoring the real world for extended stretches of time, but there is a dividend personally and in the large for doing so that makes it worthwhile (virtually always, despite some mathematics seeming ten steps removed from reality).Julzes (talk) 05:12, 28 December 2009 (UTC)

Limit of a sequence

Let {x_n} be a sequence with $\lim _{n\rightarrow \infty }{\frac {x_{n}}{n}}=g$ with g>0. How to prove the fact that $\lim _{n\rightarrow \infty }{\sqrt[{n}]{x_{n}}}=1$? --84.62.197.235 (talk) 11:24, 27 December 2009 (UTC)

First do it in the case $x_{n}:=n$ (to this end you may write the inequality of arithmetic and geometric means with the n numbers $a_{1}=\dots =a_{n-2}:=1,a_{n-1}=a_{n}:={\sqrt {n}})$. For the more general case observe that ${\frac {g}{2}}n\leq x_{n}\leq 2g\,n$ for large n; then use the former case and a sandwich argument. --pma (talk) 11:42, 27 December 2009 (UTC)

(Edit Conflict) Let $g>0$ and let $x_{n}=gn$ for all $n\in \mathbb {N}$. Do you accept that $\lim _{n\rightarrow \infty }{\sqrt[{n}]{x_{n}}}=1$ (Proof: $\lim _{n\rightarrow \infty }{\sqrt[{n}]{x_{n}}}=\lim _{n\rightarrow \infty }{\sqrt[{n}]{g}}{\sqrt[{n}]{n}}=\lim _{n\rightarrow \infty }{\sqrt[{n}]{n}}\cdot \lim _{n\rightarrow \infty }{\sqrt[{n}]{g}}=1\cdot 1=1$)? Now apply this intuition to prove your claim. --PST 11:44, 27 December 2009 (UTC)

One of the problems with your approach is that $x_{n}\not =gn$ (Igny (talk) 15:33, 27 December 2009 (UTC))

It was not intended to be a formal proof; rather it was intended to guide the intuition (and my x_n was not intended to be the same sequence as the OP's x_n; I defined a specific sequence). There is really no purpose in proving the value of a limit unless you have some idea as to how to obtain the value. The sequence x_n that I defined, and its limit, motivates the OP's question, and provides some intuition. But of course, this is guided with the assumption that the OP did not have any idea as to how to solve the problem initially (so pma's response, in that case, might have been what the OP was looking for). --PST 01:16, 28 December 2009 (UTC)

My solution turned out to be in line with PST's. (I didn't see his before I worked out the problem.) Write $x_{n}^{1/n}=n^{1/n}({x_{n} \over n})^{1/n}$. The right goes to 1 since $x_{n} \over n$ doesn't blow up. (So, the existence of a limit is unnecessarily strong.) More conceptually, the hypothesis means $x_{n}$ has the same asymptotic behavior as $n$. So, it is quite natural that we have $x_{n}^{1/n}\to 1$. -- Taku (talk) 23:34, 30 December 2009 (UTC)

Let {x_n} be a sequence with $\lim _{n\rightarrow \infty }x_{n}=g$ with g>0. How to prove the fact that $\lim _{n\rightarrow \infty }{\sqrt[{n}]{x_{n}}}=1$? --84.62.197.235 (talk) 14:22, 27 December 2009 (UTC)

Since x_n converges to g>0, you have ε<x_n<1/ε for some number ε>0 and for all n large enough, hence also ε^1/n<x_n^1/n<1/(ε^1/n). As you can see, the sandwich principle allows you to reduce your problem to the case of x_n=c>0 a positive constant. Is that clear? Then, can you do it for the case x_n=c>0? Take a logarithm for instance. --pma (talk) 13:52, 28 December 2009 (UTC)

Computationally expensive problems

Could you give examples of things that are expensive to solve but easy to check. I'd like to know the best solve/check ratio even if it's not well defined, but just any examples would be useful. --93.106.33.14 (talk) 14:32, 27 December 2009 (UTC)

Anyone with a piece of paper and pencil can calculate a product of two integers to verify the solution to a factorization problem (given time and persistence that can be done even for numbers with thousands of digits). The factorization problem for big integers however requires a lot of computational power, and modern supercomputers start chocking at factorization of 100 digit numbers. (Igny (talk) 15:57, 27 December 2009 (UTC))

All NP-complete problems (probably) have this property. Algebraist 16:55, 27 December 2009 (UTC)

Here's a stab at a well-defined ratio: RSA numbers says that the RSA-200 factoring challenge was solved using "the equivalent of 75 years work for a single 2.2 GHz Opteron". The solution was found 14 years after the problem was presented. Verifying its correctness takes less than 3 milliseconds on my computer. So that's a ratio of at least 75*365*24*60*60*1000/3 = ~788 billion in the amount of processor time used. 98.226.122.10 (talk) 03:00, 28 December 2009 (UTC)

Can someone explain to me why RSA number RSA-576 can be factored but RSA-180 and RSA-190 has not been factored yet? Isn't 576 much bigger number than 180 or 190? 122.107.207.98 (talk) 22:39, 31 December 2009 (UTC)

As RSA numbers says, RSA-576 is a 576-bit number (see binary numeral system). RSA-180 and RSA-190 have 180 and 190 decimal digits. RSA-576 has 174 decimal digits. All the decimal and binary sizes are at RSA Factoring Challenge. The RSA challenge numbers become harder to factor the larger they are, but they are not always factored in increasing order. Some people choose to not go after the smallest and easiest unfactored number. Maybe they prefer the newer challenges with bit-sized numbers which may look more relevant to cryptography. Or maybe they like an impressive round record like RSA-200 with 200 digits. PrimeHunter (talk) 23:01, 1 January 2010 (UTC)

The all-ones vector, and how to notate it

What's the most common way of writing the all-ones vector, that is, the vector, when projected onto each standard basis vector of a given vector space, has length one? The zero vector is frequently written ${\vec {0}}$, so I'm partial to writing the all-ones vector as ${\vec {1}}$, but I don't know how popular this is, and I don't know if a reader might confuse it with the identity matrix. I'm writing for a graph theory audience, if that helps pick a notation. --Bkkbrad (talk) 20:36, 27 December 2009 (UTC)

(1, 1, 1, ..., 1) ? I just had need of one in sixth dimension and actually wrote (1, 1, 1, 1, 1, 1). They don't come up very often, depending on you having made a choice of basis whereas most vector theory is designed to be independent of basis. I've not done any graph theory for a long time though. checking Adjacency matrix#Properties there's one like my first example, so maybe graph theory is not that different.--JohnBlackburne (talk) 20:53, 27 December 2009 (UTC)

I've mostly seen the notation ${\underline {1}}$, ${\vec {1}}$ or $\mathbf {1}$ (depending on your style for vectors). I believe I've seen ${\boldsymbol {\iota }}$ (bolded iota) used once or twice as well. Another alternative notation may simply be $\mathbf {e}$ (depending on your preferred vector style of course) - the rationale being that $\mathbf {e_{1}} =(1,0,\dots ,0)$ and $\mathbf {e_{2}} =(0,1,0,\dots ,0)$ and so on - although I've seldom encountered it and would avoid it as $\mathbf {e}$ is not of unit length by this definition. I do not think any of these will be confused with the identity matrix, which is usually $I$. All this is mostly from a statistical background. x42bn6 Talk Mess 02:46, 29 December 2009 (UTC)