Wikipedia:Reference desk/Mathematics

Welcome to the mathematics section
of the Wikipedia reference desk.

skip to bottom

Select a section:

• Computing
• Entertainment
• Humanities
• Language
• Mathematics
• Science
• Miscellaneous
• Archives

Want a faster answer?

Main page: Help searching Wikipedia

   

How can I get my question answered?

• Select the section of the desk that best fits the general topic of your question (see the navigation column to the right).
• Post your question to only one section, providing a short header that gives the topic of your question.
• Type '~~~~' (that is, four tilde characters) at the end – this signs and dates your contribution so we know who wrote what and when.
• Don't post personal contact information – it will be removed. Any answers will be provided here.
• Please be as specific as possible, and include all relevant context – the usefulness of answers may depend on the context.
• Note:
  • We don't answer (and may remove) questions that require medical diagnosis or legal advice.
  • We don't answer requests for opinions, predictions or debate.
  • We don't do your homework for you, though we'll help you past the stuck point.
  • We don't conduct original research or provide a free source of ideas, but we'll help you find information you need.

Ready? Ask a new question!

How do I answer a question?

Main page: Wikipedia:Reference desk/Guidelines

• The best answers address the question directly, and back up facts with wikilinks and links to sources. Do not edit others' comments and do not give any medical or legal advice.

See also:

• Teahouse
• Help desk
• Village pump
• Help manual

September 17

Normalizing logarithmic lines

I have a bunch of logarithmic equations in the form y=a ln(x)+b. In some cases, a and b are in the range of 1,000,000 to 10,000,000. In others, they are on the range of 100 to 1,000. Is there a "proper" way to normalize these so that they can be graphed together and compared. I am looking at similarities in the curve. Because of my requirement, I considered graphing y=(a/b) ln(x), which would make the y intercept the same for all of the graphs. Note: The x-scale is the same for all graphs: 1 to 100. -- kainaw™ 19:23, 17 September 2011 (UTC)

Update: Because I'm looking at probability distributions with vastly different population sizes, I think that using Zipf–Mandelbrot law may be a better method of comparison than comparing the logarithmic trend lines. The trick is to convert something like f(x)=-10278.8 ln(x)+48873.6 to a Zipfian form. -- kainaw™ 19:34, 17 September 2011 (UTC)

Finding the transformations of a matrix

Moved from Wikipedia talk:WikiProject Mathematics

The paragraph http://en.wikipedia.org/wiki/Transformation_matrix#Finding_the_matrix_of_a_transformation explains how to find the matrix belonging to a linear map. But how do I find the transformations that belong to a given matrix, which means finding the angle of rotation, scale factor and so on for the basic transformations? In other words: how to decompose a matrix into the basic transformations mentioned in said paragraph. — Preceding unsigned comment added by 84.157.37.3 (talk) 16:01, 17 September 2011 (UTC)

You might try Jordan normal form, especially the section on real matrices.--RDBury (talk) 20:02, 17 September 2011 (UTC)

I'm not sure that that's what the OP's after. Putting a matrix into Jordan normal form is done by changing the basis. I think the OP wants to write a given linear transformation, with respect to a given basis, as the composition of a rotation, a shear transformation, a reflection, a dilation, etc. I'm not sure that there's a unique answer either. Matrix multiplication isn't commutative and any fixed matrix can be written as uncountably many products of pairs of matrices. — Fly by Night (talk) 21:15, 17 September 2011 (UTC)

If the 2x2 matrix in question is of the form $e^{X}$, then

$X=a{\begin{bmatrix}1&&0\\0&&1\end{bmatrix}}+b{\begin{bmatrix}1&&0\\0&&-1\end{bmatrix}}+c{\begin{bmatrix}0&&1\\1&&0\end{bmatrix}}+d{\begin{bmatrix}0&&-1\\1&&0\end{bmatrix}}$

Here $e^{a}$ is the dilation factor, $e^{b}$ and $e^{c}$ are shear factors, and d is the rotation angle. Reflections are not of the form $e^{X}$, I think. Bo Jacoby (talk) 23:58, 17 September 2011 (UTC).

Any matrix can be (basically uniquely) written as a strain followed by a (improper) rotation. This is the polar decomposition. Sławomir Biały (talk) 00:18, 18 September 2011 (UTC)

September 18

Continuous function

Is there a non-uniformly continuous bounded real valued function defined on all real numbers? Money is tight (talk) 02:06, 18 September 2011 (UTC)

Sin(x^2) is an example of such a function. Sławomir Biały (talk) 02:27, 18 September 2011 (UTC)

Thanks! I have another question. If f is a continuously twice differentiable function on the real line with compact support, is it the fourier transform of some L^1 function? Money is tight (talk) 06:41, 18 September 2011 (UTC)

Yes. You can estimate the inverse Fourier transform of f by $C(1+x^{2})^{-1}$, which is L^1. Sławomir Biały (talk) 11:10, 18 September 2011 (UTC)

I don't fully understand what you mean. By C do you mean a constant? How and in what sense is the estimation (uniform pointwise L^1 L^2 norm etc.)? Is the inverse transform in L^1? Money is tight (talk) 01:25, 19 September 2011 (UTC)

(Simple?) projectile motion

This is an apparently simple problem which seems to involve algebra of frustrating complexity. A particle is projected from the top of a cliff of height h metres with a velocity of V m/s into the sea. What is its maximum horizontal range? The equations of motion are

$x=Vt\cos \theta ,\qquad y=-{\frac {g}{2}}t^{2}+Vt\sin \theta +h$

where θ is the angle of projection and the variable in question. There are two obvious approaches: Find the larger root T of y(t) = 0 and maximise x(T) in terms of θ; or rewrite y as a function of x and maximise the larger root X of y(x) = 0 in terms of θ. Both are very algebra-heavy and I keep getting lost. A craftier approach might be to maximise the roots of y(x) = 0 with product and sum examination rather than actual computation, where

$y(x)={\frac {-g}{2V^{2}\cos ^{2}\theta }}x^{2}+x\tan \theta +h,$

but that hasn't yielded me much joy. Any advice is appreciated; is there something simpler I'm missing? —Anonymous Dissident^Talk 12:47, 18 September 2011 (UTC)

The problem is basically an exercise in seeing things through to the end. Solve y=0 for t, keeping the positive root only, and substitute back into x. You then get x as a function of theta, which can be maximized by methods of one variable calculus. Details are in the article Range of a projectile. Sławomir Biały (talk) 12:59, 18 September 2011 (UTC)

I think the problem can be simplified a bit by noticing that the point of maximum distance would be on the envelope of the parabolas which are the various trajectories. To get the envelope, set (dx/dt)(dy/dθ)=(dx/dθ)(dy/dt) to get an additional equation, I get v=g t sin θ. This can be plugged in to y=0 to get a linear equation for sin θ, and both of these can be plugged into the equation for x to get the maximum distance. Or you can just find the equation of the envelope, which is another parabola, and solve for y=0.--RDBury (talk) 13:54, 18 September 2011 (UTC)

Slight correction, I should have said "linear equation for sin² θ". Also, since the envelope is a parabola, it has a focus which, interestingly imo, is the location of the cannon.

That's pretty clever. Starting from Anonymous Dissident's equation

$y(x)={\frac {-g}{2V^{2}\cos ^{2}\theta }}x^{2}+x\tan \theta +h,$

if we make a change of variables $\tau =\tan \theta$, this gives the family of parabolas indexed by τ:

$P_{\tau }:\quad y={\frac {-g}{2V^{2}}}(1+\tau ^{2})x^{2}+\tau x+h$

A point (x,y) is on the envelope if and only if it is on a pair $P_{\tau },P_{\tau +d\tau }$ of infinitely near parabolas in the family. So, for such a point,

$0={\frac {-g}{V^{2}}}\tau d\tau x^{2}+d\tau x\implies x=V^{2}/(g\tau )$

(the nontrivial zero). Plugging into the equation for y(x) gives

$y(V^{2}/(g\tau ))=h+{\frac {V^{2}(\tau ^{2}-1)}{2g\tau ^{2}}}$

Solving for y=0 gives

$\tau ={\frac {V}{\sqrt {2gh+V^{2}}}}.$

So the envelope hits the ground at

$x={\frac {V^{2}}{g\tau }}={\frac {V}{g}}{\sqrt {2gh+V^{2}}}.$

(This doesn't seem to agree with the answer Range of a projectile gives. I think there must be an error in the article somewhere.) Sławomir Biały (talk) 19:05, 18 September 2011 (UTC)

An algebraic approach, which may be what was requested, is this. A characteristic length is $L$ defined by $V^{2}=Lg$. Introducing the dimensionless variable $z$, and the dimensionless height $b$, by substituting $x=Lz$ and $h=Lb$ and $y=0$ into Anonymous Dissident's equation, gives

$0={\frac {-g(Lz)^{2}}{2Lg\cos ^{2}\theta }}+Lz\,\tan \theta +Lb.$

Dividing by $L$, and multiplying by $2\cos ^{2}\theta$ gives the simpler equation

$0=-z^{2}+2\,z\,\sin \theta \cos \theta +2\,b\,\cos ^{2}\theta .$

This is further simplified by the trigonometric identities for the double angle $\alpha =2\,\theta$

$0=-z^{2}+z\,\sin \alpha +b\,\cos \alpha +b.$

Another equation is obtained by differentiation,

$0=-2z\,dz+\sin \alpha \,dz+z\,\cos \alpha \,d\alpha -b\,\sin \alpha \,d\alpha .$

When $z$ is maximum the differential $dz$ is zero even if $d\alpha$ is not. So

$0=z\,\cos \alpha -b\,\sin \alpha .$

Define $C=\cos \alpha$ and $S=\sin \alpha .$ Then the system of equations is completely algebraic

$0=-z^{2}+zS+bC+b=zC-bS=C^{2}+S^{2}-1\,.$

It remains to eliminate $C$ and $S$ to get an algebraic equation in $z$ alone. Bo Jacoby (talk) 02:20, 19 September 2011 (UTC).

In order to avoid making sign errors while manipulating polynomials I temporarily use the name $m$ to signify $-1$. So $m+1=0$ and $m^{2}=1$. The minus sign $-$ is then not used.

The three polynomials

$P_{1}=mz^{2}+zS+bC+b$

$P_{2}=zC+mbS$

$P_{3}=C^{2}+S^{2}+m$

all evaluate to zero for the wanted values of the variables $z,C,S$ and the known values of the constants $b,m$. By construction the following polynomials also evaluate to zero.

$P_{4}=(zC+bS)P_{2}+b^{2}P_{3}=(z^{2}+b^{2})C^{2}+mb^{2}$

$P_{5}=(mz^{2}+mzS+bC+b)P_{1}+z^{2}P_{3}$

$=(mz^{2}+mzS+bC+b)(mz^{2}+zS+bC+b)+z^{2}(C^{2}+S^{2}+m)$

$=(mz^{2}+bC+b)^{2}+mz^{2}S^{2}+z^{2}C^{2}+z^{2}S^{2}+z^{2}m$

$=(mz^{2}+bC+b)^{2}+z^{2}C^{2}+z^{2}m$

$=b^{2}C^{2}+(mz^{2}+b)^{2}+2bC(mz^{2}+b)+z^{2}C^{2}+z^{2}m$

$=(z^{2}+b^{2})C^{2}+2b(mz^{2}+b)C+(mz^{2}+b)^{2}+z^{2}m$

Here $S$ has been eliminated. Substitute $w=z^{2}$.

$P_{4}=(w+b^{2})C^{2}+mb^{2}$

$p_{5}=(w+b^{2})C^{2}+2b(mw+b)C+(mw+b)^{2}+mw$

Now eliminate $C^{2}$ from the equations $0=P_{4}=P_{5}$.

$P_{6}=mP_{4}+P_{5}$

$=m((w+b^{2})C^{2}+mb^{2})+(w+b^{2})C^{2}+2b(mw+b)C+(mw+b)^{2}+mw$

$=b^{2}+2b(mw+b)C+(mw+b)^{2}+mw$

$=2b(mw+b)C+w^{2}+m(2b+1)w+2b^{2}$

Now eliminate $C$ from the equations $0=P_{4}=P_{6}$.

The above calculation is unfinished. I have deleted some errors. Bo Jacoby (talk) 05:12, 23 September 2011 (UTC) .

September 19

Different Types of Integrals and Derivatives

I understand that there are several different types of integrals like the Riemann integral, Lebesgue integral, Cauchy, Wiener, Feynman, etc. Are there different kinds of derivatives too? What are they? I only know of standard Calc I derivative (with the gradient as a generalization) but can we consider the divergence and the curl as types of derivative too? Any others? 67.40.134.8 (talk) 01:57, 19 September 2011 (UTC)

Wikipedia has an article on everything—or, in this case, a category. See Category:Generalizations of the derivative. —Bkell (talk) 04:04, 19 September 2011 (UTC)

Oh, wait, there's an article too: Generalizations of the derivative. —Bkell (talk) 04:06, 19 September 2011 (UTC)

Three person oblivious transfer

Alice, Bob and Charlie each have a secret. Is there a way for each of them to know all 3 secrets, without any of them knowing which of the two other secrets belong to whom, and without involving an other party? -- Meni Rosenfeld (talk) 08:12, 19 September 2011 (UTC)

Perhaps you wanted a more computational answer, but real life you could write them down, put them in a bag, shuffle and pull out again, allowing everyone to read all three. Is there an equivalent relevant to the context of your question? Grandiose (me, talk, contribs) 08:35, 19 September 2011 (UTC)

I am indeed looking for a computational answer, because this is supposed to happen via internet communication without meeting physically. I'm thinking mostly of a protocol where the primitives are sampling random bits and sending messages from one party to another, assuming availability of encryption and digital signatures.

I've now realized this is possible if we assume availability of an anonymyzation network such as Tor. A sends his secret to C anonymously with a digital signature that could be either A's or B's (I think there are protocols for that). Likewise for all 6 pairs. Then all C has is two messages with two secrets, each of them must be either A's or B's but he doesn't know which is which.

Is this still possible if we require all messages to be unambiguously digitally signed? -- Meni Rosenfeld (talk) 09:27, 19 September 2011 (UTC)

Alice picks two private keys for a one-way, commutative encryption technique. She sends one public key to Bob and one to Charlie. They both encrypt their secrets with the public key, then the men exchange encrypted secrets. They both encrypt the received secrets a second time, then Charlie sends Bob's doubly encrypted secret back to Bob. Bob sends both doubly encrypted secrets to Alice, in random order. Alice decrypts both, then sends all three secrets to both men, in random order. Wouldn't this do it?--Antendren (talk) 12:06, 19 September 2011 (UTC)

That won't work. Alice has two encryption keys. When she gets the messages back, she knows which is which because they use two different keys. If you correct this and use the same key for each one, Bob has both messages encrypted with the same key. Once he gets all the messages, he can encrypt them to see which one comes from who. -- kainaw™ 12:58, 19 September 2011 (UTC)

The encryption is commutative, so Alice doesn't know if a message was encrypted with key 1 and then key 2 or the other way around. -- Meni Rosenfeld (talk) 14:32, 19 September 2011 (UTC)

Looks correct to me, thanks. Do you know if this has a name?

Now for the next problem: Obviously if Alice and Bob collude, they can find out Charlie's secret and there's nothing to do about that. In the n-person case you want ideally that each person will not have any information on which of the n-1 other secrets belongs to whom. If k people collude, in theory they shouldn't which of the n-k secrets belong to whom of the n-k people out of the collusion. But I tried generalizing the 3-people procedure, and in what I came up with it's enough for 2 people to collude in order to find out everyone's secrets. Is there a protocol for the n-person case which achieves the theoretical obliviousness, or something close to it? -- Meni Rosenfeld (talk) 14:32, 19 September 2011 (UTC)

How's this for an n-person protocol: Each person chooses their own key, and they arrange themselves in a cycle. Each person encrypts their own secret, then passes it along to the next person in the cycle, who encrypts it in turn. Continue until every secret has been encrypted by every key. Then send them all to person one, who removes their own encryption from all, then sends them all to the next person in the cycle, in random order. Continue until the end of the cycle, when one person has all the plain texts, and no one knows the order. Distribute amongst the rest of the group. I think this achieves your goal, although I don't have a very good argument for the failure of collusion.

I'm sure I'm not the first person to come up with these, but I don't know what they're called.--Antendren (talk) 22:19, 19 September 2011 (UTC)

This is brilliant, thanks. However, it seems to me there is a collusion attack if we assume attackers can risk getting caught tampering with the protocol for a chance to get information. Assume 4 people and that A and D collude. At the end of the first cycle, each person has his own secret encrypted with all keys. Each sends this item to A, who knows which item contains whose secret based on who send it to her. Then A knows A(ABCD) (A's secret encrypted with all 4 keys), B(ABCD), C(ABCD) and D(ABCD). She is supposed to send to B A(BCD), B(BCD), C(BCD) and D(BCD) in a random order. Instead she sends A(BCD), B(BCD), C(ABCD) and D(BCD). B follows protocol and sends to C A(CD), B(CD), C(ACD), D(CD), and C sends to D A(D), B(D), C(AD), D(D). D doesn't know which of B(D), C(AD) is which, so he decrypts one in random with A's key. He sends to everyone A, D and either {B, C} or {B(A^(-1)), C(A)}. If he guessed right nothing is suspected and A and D know B and C's secrets. If he guessed wrong then B and C complain that their secrets aren't in the published set and abort - in which case their secrets are revealed to A and D, but for my application it does them no good if they abort.

This is getting a bit specific to my application so I'll try to take it from here. But of course if you happen to come up with something without such an attack (yourself or with a reference) it would be great. -- Meni Rosenfeld (talk) 07:30, 20 September 2011 (UTC)

Ooh, that's interesting. In fact, I think there's a modification that ensures A and D get away with it: A instead sends B(BCD), C(ABCD), D(BCD) and C(BCD). Then D receives B(D), C(AD), D(D) and C(D). He decrypts them all with A to see which matches up, telling him which is C and which is B. Then he sends A, B, C, D to everyone, because A provided him with her secret. In general, tampering of this nature will always work as long as the conspiracy contains the first and last people, and at least half the people total: A sends two copies of every message the conspiracy doesn't know, one as she's supposed to, one which has been tagged in some way (perhaps by repeated applications of A's encryption). Then D applies the appropriate decryptions to see which are which. I don't see a way around this.--Antendren (talk) 08:07, 20 September 2011 (UTC)

I came up with all sorts of crazy ideas, some of which I thought for a while would work, but turned out not to. One direction I thought about was recursion - assume it is possible for n, and do something where A has a similar role to the 3-person case and the other n people share information between them obliviously. One of the many problems was that the requirements of the protocol to be suitable to serving in induction hypothesis capacity are stricter than what I need for the original problem. -- Meni Rosenfeld (talk) 14:17, 20 September 2011 (UTC)

Okay, now for a completely different approach, one without encryption. When things begin, each person waits a random amount of time (chosen by some distribution with no smallest possible time), then sends their message to someone else at random. Whenever a person receives a message, they wait a random amount of time and send it off to someone at random. After some large amount of time, everyone who is currently holding a message (has received but not yet sent on) distributes that message to everyone in the group. Now, no one can tell where a message originated from, although you can put a probability distribution on it. After all, the message you just received might have originated with the sender, or they might have gotten it from someone else. So collusion can give you a high confidence that a certain message originated with someone, but never certainty.--Antendren (talk) 09:25, 20 September 2011 (UTC)

I don't know if this will hold up in practice. People are incentivized to alter what and when they send in order to keep their own secret secure. Committing to a random seed won't help since verifying that they acted according to protocol requires revealing enough information to learn people's secrets (and is difficult anyway due to the unpredictable nature of communication networks).

If there is a way to implement this where only a small amount of information is leaked, though, it will be acceptable. -- Meni Rosenfeld (talk) 14:17, 20 September 2011 (UTC)

Also note... The "put them in a bag" solution won't work. The bag is a third party, which the question states cannot be used. I do not believe this is solvable. At some point, someone has to send something to someone. As soon as the initial transfer takes place, one person knows his or her own message and the message received. So, anonymity is removed. -- kainaw™ 14:20, 19 September 2011 (UTC)

Yes, the bag is kind of a third party. But more specifically what I want to restrict is a third party that could publish the secrets. A bag can't do that.

Your proof of impossibility assumes that from the first message it is possible to deduce the sender's secret, but with encryption and randomization that's not at all guaranteed. Cryptography is very powerful stuff. -- Meni Rosenfeld (talk) 14:39, 19 September 2011 (UTC)

Cryptography can be useful, but it usually isn't all it is cracked up to be - especially when each person knows both the encrypted message and the plain text message. So, I have three messages. One is mine - I know that. The other two belong to two other people. I also have two encrypted messages that match up to those plain text messages. I know the method of encryption used. I also see some key info passing around. With a little fiddling, I quickly re-encrypt the plain text messages and I know who sent what. -- kainaw™ 14:49, 19 September 2011 (UTC)

I think you should reread Antendren's protocol. -- Meni Rosenfeld (talk) 15:14, 19 September 2011 (UTC)

The limitation is that given a protocol, an encrypted message, and two plain text messages, it is not difficult to identify which plain text message is the encrypted one. You don't need to completely encrypt/decrypt anything. You just need to do a little of it to get a correlation. Of course, you could say that you are going to use a protocol that doesn't currently exist that avoids this problem. Perhaps you plan to use quantum encryption. But, if that exists, quantum hacking should exist also - which makes it even easier to guess the key used in the process. -- kainaw™ 16:20, 19 September 2011 (UTC)

I don't understand this objection. You're Bob. You have two plain texts, one of which is Alice's and one of which is Charlie's, but you don't know which is which. You also have cypher text that you know is Charlie's secret, but you don't know the public key used in the encryption (`public key' is unfortunate terminology here). How do you determine which is Charlie's plain text?--Antendren (talk) 22:19, 19 September 2011 (UTC)

Just try it. Pick a protocol. Encrypt two plain texts with two different keys. Then, try it again with, say, 25% of the key correct. Take note of how you can detect similarities between the cypher text using the whole key and the cypher text with part of the key correct. Then, consider this scenario again. You are sharing encrypted text, public keys, and complete plain texts. -- kainaw™ 12:36, 20 September 2011 (UTC)

For those who don't want to do it, here's an example: I have two texts:

1. This is the first plain text.
2. Nothing in this text is anything like the first text.

In encrypt the first with AES (Rijndael) 256-bit key encryption using the key "password".

I then encrypt both files using the same scheme, but the password "pass1234".

The bit-by-bit comparison of the first text using "pass1234" to the first text using "password" is an 88% match. The bit-by-bit comparison of the second text using "pass1234" to the first text using "password" is a 78% match. Of note: There is still a 10% discrepancy between the two if you use "pass" instead of "pass1234". -- kainaw™ 12:50, 20 September 2011 (UTC)

I'm not very familiar with cryptography (-ology?), so this is probably wrong, but couldn't Alice create a public and private key and give it to Bob and Charlie. Bob and Charlie create a public and private key that they both share, and use that to sign both secrets? (Repeat for both Bob and Charlie). KyuubiSeal (talk) 15:43, 19 September 2011 (UTC)

Can you be more specific? How will Bob and Charlie sign their two secrets without one of them learning the other's secret? -- Meni Rosenfeld (talk) 17:44, 19 September 2011 (UTC)

If they both know their shared private key, isn't that all they need? Then once they're encrypted, have them send either their own, or each other's, (selected randomly). They're using the public key Alice sent for encryption, so they can't decrypt each other's. (There's six sets of keys, three known by only one person, used for encryption, and three known by pairs, used for signing. Probably really really inefficient, but again, I don't have any experience. :\ ) KyuubiSeal (talk) 01:04, 20 September 2011 (UTC)

Yeah, looks like that will work. Unless I'm missing something, this is similar to Anendren's first suggestion, but simpler. Thanks. -- Meni Rosenfeld (talk) 07:30, 20 September 2011 (UTC)

Wait, no, that won't work. Once the secrets are known, Bob will try to encrypt all 3 with Alice's public key until he finds one that matches Charlie's encrypted secret. Then he knows this secret is Charlie's. -- Meni Rosenfeld (talk) 14:17, 20 September 2011 (UTC)

It took a bit of searching and I finally found what you want in a student's paper from a class a while back. First, you need a secure encryption function that allows you to encrypt and decrypt with multiple keys out of order. For example, if I encrypt with key A and then add text to it and encrypt with key B, I can decrypt the first part of the message by decrypting both with key A (somehow, this will do nothing to the second part which was never encrypted with key A - which is why I didn't give this paper a high grade). Assuming that works, here goes: Alice encrypts her message and sends it to Bob. Bob adds his before or after hers (randomly). He encrypts the whole thing and sends it to Charlie. Charlie adds his to the beginning or end (randomly) and encrypts the whole thing. He sends it to Alice. She decrypts it with her key, which only partially decrypts her message. She sends it to Bob. He decrypts with his key which partially decrypts Alice and Bob's message. He sends it to Charlie who decrypts it with his key and gets all plain text messages. He doesn't know the order of Alice and Bob's messages. All he knows is they are before or after his. He sends all three plain text messages to Alice. She doesn't know the order of the messages either. She sends them to Bob. He doesn't know the order of the messages. I noted at the end a situation. Alice sends to Bob. Bob adds his to the bottom. He sends to Charlie. Charlie adds his to the bottom. When it comes back, Bob sees his in the middle, he knows Alice's is on top and Charlies is on bottom. The student apparently suggested that Charlie and Alice randomize the order when sending the plain text messages around. -- kainaw™ 19:23, 19 September 2011 (UTC)

Distribution of charge in 1,2,3 dimensions on symmetrical bodies

Hi. See Wikipedia:Reference_desk/Science#Surface_charge_on_a_conductor .. Having botched an answer, and then discovered that my maths skills probably aren't up to integrating to get the potential/field inside/outside a circular ring of charge (in 2dimensions) I though I should leave a note here where someone is more likely to be able to properly answer the original question.

As an aside (that I can only hope someone can answer) - it strikes me as odd, or possibly even fortuitous that only (?) in 3 dimensional euclidean space (which I inhabit) is the field inside a spherical shell of stuff exhibiting an inverse square law of field strength constant and zero. (eg Shell theorem, Gauss etc) (This must affect a lot of physics). I haven't considered the 4D case and am not requesting an answer.. Does anyone know of any philosophers/scientist etc or the like that have considered this coincidence- ie that a "3D" universe and inverse square law fields (in combination) are favoured have 'unusual propeties' in combination, over other variations .. a la the Anthropic principle. (Did that make a dot of sense to anyone??) Thanks Imgaril (talk) 13:20, 19 September 2011 (UTC)

I think that in a 4D universe the same would hold for an inverse cube law. So it's not that 3D is special, just that 2=3-1. -- Meni Rosenfeld (talk) 14:42, 19 September 2011 (UTC)

Thanks - it later occured to me that in inverse square law is probably a consequence of surface area increasing with r² in 3 dimensional space (as it states at Inverse-square_law#Justification). Similarly this would mean in 1D space intensity is proportional to distance⁰ (like a laser) which also gives a net field of zero in between equal 'charges'.

I think I will have another attempt at the integral of the ring in 2D space using a 1/r law (length of perimeter, rather than area of shell) - I suspect that this should be the same as the 3D and 1D cases - though it's not immediately apparent to me why.. I may be back in a few days asking for help... :)

Thanks again.Imgaril (talk) 16:33, 19 September 2011 (UTC)

The Newtonian potential (which governs classical fields in n dimensions) is the potential associated to a point charge. Mathematically, it is the fundamental solution of the Laplace equation. It is C/r^{n-1} in n dimensions (C log r in 1 dimension). There's nothing particularly special about 3 dimensions. Harmonic functions have similar properties in all dimenstionas. Sławomir Biały (talk) 17:24, 19 September 2011 (UTC)

I tried again the integral around the ring in 2d using a 1/r function and (got lucky this time finding it simplied to the integral of sin(x) between 0 and pi)Assuming I got it right it does indeed seem to be zero for 2D (inside the ring). That makes me feel a lot better, having one less thing to worry about. Thanks. Imgaril (talk) 21:07, 19 September 2011 (UTC)

Actually it looks like I made a schoolboy error in the integral - I'll ask a separate question.Imgaril (talk) 10:16, 20 September 2011 (UTC)

I keep coming back to this question, and it never makes sense to me.

It seems that humans are the only thing in nature that produces extremely complex abstract systems (mathematics) representing things that don't ever exist or represent our universe. Humans are also a part of our universe. And yet, somehow, the entire body of mathematics, which is huge, all is consistent. Even though no mathematical axiom comes from the physical universe, and we can never know whether any axioms are true in a physical sense, still, people imagine an axiomatic system, and then it makes sense (is consistent with itself, you can prove things within it, etc). Where does this higher order come from? I've asked many times what would happen if mathematics itself were inconsistent, such that any, even trivial, axiomatic systems turned out to be such that you could prove both statements and their opposites, but the answer I've always gotten is that this is simply not possible: that there is no way that mathematics -- even though it does not come from the physical universe -- is itself inconsistent.
There's more. I've asked about parallel worlds in which every single physical law is radically different. And yet, mathematics in that world functions exactly the same. If pi is 3.14159... here, then it is 3.14159... there, no matter how different that universe is. It is not possible for it to be so different that pi is 3.24159... Of course, pi could turn out to describe nothing physical in either our universe or any other universe, and yet pi remains fixed at 3.14159...
so where does this order and sense, which doesn't actually describe anything physical come from? Is it a window into heaven, where things can be proven and are perfect and consistent? If not "heaven" then in what realm is "math" which transcends even our very Universe?? 82.234.207.120 (talk) 22:51, 19 September 2011 (UTC)

This is the big question, yes. From my point of view as a mathematical realist, yes, it's a window into the Platonic heaven. Not everyone agrees. --Trovatore (talk) 22:54, 19 September 2011 (UTC)

what other perspective or explanation comes close to fitting the facts? I really don't like this explanation if for no other reason than that it seems several thousand years old. Come on. 82.234.207.120 (talk) 23:08, 19 September 2011 (UTC)

Well, the observed consistency could be a brute fact, with no particular reason for it. I don't find that convincing. On the other side of the coin, though, some would argue that the Platonic existence of mathematical objects might imply the observed consistency but doesn't cause it, so it doesn't really explain what causes us to observe the consistency. --Trovatore (talk) 23:13, 19 September 2011 (UTC)

I've asked a follow-up question below. 82.234.207.120 (talk) 23:16, 19 September 2011 (UTC)

(Out of curiosity, why do you feel that an explanation being old is an argument against it? --Trovatore (talk) 23:16, 19 September 2011 (UTC) )

Yes, due to prior probability. What are the chances that the ancients, who were a lot dumber, stumbled on the truth? 82.234.207.120 (talk) 23:22, 19 September 2011 (UTC)

Well, 2+2 has been 4 for a long, long time. Probability doesn't really enter into it; if something is correct, it's correct, however unlikely the source. -GTBacchus^(talk) 23:25, 19 September 2011 (UTC)

"The ancients were a lot dumber." I'm starting to think it's a bad idea to contribute to this thread. --Trovatore (talk) 00:01, 20 September 2011 (UTC)

I might have been colloquial, but the sentiment comes from bertrand russell: he writes that they didn't even properly "prove" any of their geometric proofs. not to mention things like investigative science, everything from chemistry to computers was completely unknown to them. and yet, somehow, they would have the correct conception of metaphysics? (without the scientific method to aid them in finding it). I find that exceedingly unlikely. 82.234.207.120 (talk) 00:05, 20 September 2011 (UTC)

I suggest you study the ancients directly. We can still learn a lot from them. Don't ask me what I mean until you've read Euclid, Plato, Aristotle, Ptolemy - the originals. -GTBacchus^(talk) 02:55, 20 September 2011 (UTC)

There isn't any evidence that there exists a physical universe (apart from a purely mathematical one). So, it could be that we are just algorithms that exist in the sense of pure math only. There exists an ensemble of all possible algorithms, one of these happens to describe precisely that algorithm your brain is executing right now when you read this posting. Count Iblis (talk) 15:07, 20 September 2011 (UTC)

(Note: The following is a reply to the original question, not a reply to the outdented statement directly above that isn't following standard indentation standards -- kainaw™ 16:02, 20 September 2011 (UTC))

I do not understand the claim that nothing in mathematics comes from the physical universe. Try very trivial mathematics, such as the definition of 1. If you have some object from the physical universe, such as an apple, and it is the only one you have, you can claim that you have one apple - using the mathematical term 1. You cannot claim that you have 2 or 3 or 74i apples. You have 1. Continue to counting, which is very trivial mathematics, and you can see that if you add 1 apple to 1 apple, you get 2 apples, not 3 or 8 or -5473. Everything else expands on counting. It doesn't matter how complex mathematics gets, it all goes back to counting from 1 (not zero, that came after counting). Counting comes from observations of things in the physical universe. -- kainaw™ 15:32, 20 September 2011 (UTC)

… but what is an apple on a subatomic, quantum level? It could be argued that the notion of an apple is a man made construct. — Fly by Night (talk) 15:47, 20 September 2011 (UTC)

Then assume that math does come from a "physical universe". It is then still the case that everything you know about math and everything else is represented by your brain state. Your brain doesn't contain any apples, but the information stored in the brain my contain descriptions of apples and then the description of integers may be given in terms of the description of apples. However, the "apple part" of the description of integers is redundant. To extract the integers from your brain, you would have to throw that part away.

In fact, to define what you really are, you would have to extract the algorithm that your brain is running from the physical brain, so in the end you are abstract math yourself. That then casts doubt on the very premise that a physical universe exists. Count Iblis (talk) 15:47, 20 September 2011 (UTC)

I do not read this question as asking the age-old philosophical question of "what is reality?". I see it as asking us to accept that absolutely nothing from mathematics is based on anything at all in the physical universe and then asking a question. I don't agree with the claim that absolutely nothing from mathematics is based on anything at all in the physical universe. -- kainaw™ 16:01, 20 September 2011 (UTC)

how would mathematicians react if math had human, contemporary meaning?

for a book I'm writing, what is the probable reaction of the mathematical community if it turned out that math had obvious human, contemporary meaning? For example, if you calculated pi in a certain base and just interpreted the results as unicode, it would magically be perfect English prose, just an endless tome as long as you wanted to calculate it. "Couldn't God communicate with us this way?" Well, no, because not even God can change the value of pi. But that doesn't make sense to me -- because "obviously" a hypothetical Creator has control over the value of Pi. But isn't it the case that it is simply MEANINGLESS to talk of "control" over the value of pi? It doesn't "mean anything" to change it. And yet, there it is, a certain specific value... I find it irreconcilable that it has a certain specific value while having to believe that it could not be another way. Pi is not a round enough value that it "could not be any other value". And yet that is exactly what math holds: that it could not possibly be any other value -- not even God himself could create a universe in which pi was otherwise. This is so strange. But, back to the question: what would the mathematical community's likely reaction be to having an obvious, human-readable meaning in Pi that was directly relevant to contemporary humanity, and readable as prose? --- note, you might have to use your imagination for hte mechanism, as pi has certain characteristics that would make it impossible for it to literally be encoded text...but if the encoding were complex enough (not just "interpreted in a certain base as unicode") it should still be possible.... thanks for your perspective. 82.234.207.120 (talk) 23:15, 19 September 2011 (UTC)

But π, when encoded in base 64, does contain readable prose! We just haven't written down enough digits yet. 108.3.68.183 (talk) 23:37, 19 September 2011 (UTC)

That might be true if the digits of pi were truly random. Dbfirs 22:35, 20 September 2011 (UTC)

The digits are certainly not literally random. It would be astonishing, though, if they weren't random enough to make 108's claim true. --Trovatore (talk) 22:37, 20 September 2011 (UTC)

Although almost all numbers on the number line are Normal numbers, almost all of the ones in everyday use are not. It has not yet been possible to determine whether or not pi is normal. Dbfirs 07:09, 25 September 2011 (UTC)

Right - and what I'm saying is, that if that readable prose started at, say, precisely the trillionth digit, and then continued uninterrupted indefiitely, as uninterrupted English prose -- well, every mathematician in the world would simultaneously shit themselves. That much is clear. But then what? What would their intellectual reaction be afterward? You're all mathematicians here: how would you react? 82.234.207.120 (talk) 23:43, 19 September 2011 (UTC)

Dick Feynman has a useful quote related to this, from The Meaning of It All. "I had the most remarkable experience this evening. While coming in here I saw license plate ANZ 912. Calculate for me, please, the odds that of all the license plates in the state of Washington I should happen to see ANZ 912." The odds! They're nearly impossible! Nimur (talk) 23:53, 19 September 2011 (UTC)

Yeah, I think you're not getting the question. 82.234.207.120 (talk) 23:59, 19 September 2011 (UTC)

I think you're placing arbitrary meaning on a random string of numbers, and expecting the rest of the world to share your arbitrary teleology. You might be surprised to know that lots of people do this: numerology exists because people don't understand numbers, so they mysticize them. Famous scientists like Feynman got asked questions like yours so often... that they wrote entire books about it. There's no meaning in random strings of numbers, other than the meaning you place on it. Nimur (talk) 00:03, 20 September 2011 (UTC)

That reminds me of a joke: One probabilist throws a dart at a board, and turns to a second probabilist, who is a Bayesian, and asks "What's the probability that the dart would have hit that point?" To which the second probabilist responds: "One." 108.3.68.183 (talk) 00:05, 20 September 2011 (UTC)

clarification of question

I don't mean that you can somehow interpret the numbers in some forced way. I mean, like this: http://xkcd.com/10/ except instead of "help I'm stuck in a universe factory" you have a hundred page book, and then a thousand page book, and then a million page book... as long as you continue decoding you get more and more and more nonrepeating, perfectly rendered English text. Obviously that is not numerology. And just as obviously that would never actually happen...but what if it did? what would the reaction be then? 82.234.207.120 (talk) 00:12, 20 September 2011 (UTC)

Well first everyone would think you are just selecting random noise (e.g. infinite monkeys). If you can convince people that isn't true, then it would certainly be surprising (the digits of pi are not random?!?!). Many people would suddenly be very interested in computing more digits of pi than ever before. Beyond that it would obviously depend on what the message is. But in general, I suspect theologians and similar types would be more excited than mathematicians. Dragons flight (talk) 00:31, 20 September 2011 (UTC)

I'm telling you there is no selection going on. It would be sequential, someone would discover that using such and such an encoding, arbitrary amounts of SEQUENTIAL message appear, all perfectly rendered English. 82.234.207.120 (talk) 01:10, 20 September 2011 (UTC)

This is related to the question above, by the way. What I'm interested in, is, how would we explain this metaphysically. 01:11, 20 September 2011 (UTC) — Preceding unsigned comment added by 82.234.207.120 (talk)

If pi digits are random, then somewhere in it you can almost certainly find a sequential code for the entire King James Bible, but that is simply the nature of randomness and not a message from God. So the first concern will always be showing that the effect is not random. But even assuming there is a non-random message in there, why would mathematicians be the ones to "explain" it? Metaphysics is the realm of theologians and philosophers, not mathematicians. Dragons flight (talk) 01:30, 20 September 2011 (UTC)

No, you almost certainly CAN'T *actually* find a place with that. Moreover, even if you did have a method for findind an arbitrary text (such as the king's james bible), what followed it would be gibberish. in my scenario, there is a spot that is easy to describe (e..g "trillinoth digit"), and with a certain encoding, starting in that stop it starts making sense and doesn't stop. whether you read a thousand or a million pages, it's all unique and meaningful human text ('from god'). what would a mathematician's metaphysical reaction be to such a turn of events? 82.234.207.120 (talk) 01:44, 20 September 2011 (UTC)

Yes, if it goes on long enough, and the digits are truly random, it must come up at some point. I believe someone mentioned the infinite monkeys example? What's so special about a trillion? Now, if the text never stopped making sense, that would be something. And as to the question, it depends on the person. You might say "I knew it!", while I might be double checking the digit generation / decoding I used for 'Easter egg'-like things. KyuubiSeal (talk) 03:42, 20 September 2011 (UTC)

I think 82's point is that, even if that point in the decimal expansion of π exists, you still almost certainly (in the colloquial sense not meaning almost surely) can't "actually find it". That's quite true. --Trovatore (talk) 04:59, 20 September 2011 (UTC)

But what if frogs really did have wings? What then?!? The answer: you'd have to find another hobby, 82.234.207.120. -GTBacchus^(talk) 05:59, 20 September 2011 (UTC)

This discussion reminds me of the segment of Contact (novel) where they discover a pattern deep within Pi. ←Baseball Bugs ^{What's up, Doc?} carrots→ 06:16, 20 September 2011 (UTC)

Here is a more serious response:

1. The infinite sequence of pi digits - is an infinite sequence that is mechanically computable.

2. The infinite sequenece - which (under Unicode) constitutes the infinite text of King James Bible (followed by itself again and again forever) - is an infinite sequence that is mechanically computable.

Conclusion: there is a finite code (e.g. a finite formula or a finite computable algorithm) which reflects a one-to-one correspondence - between the infinite sequence of pi digits - and the infinite sequenece which (under Unicode) constitutes the infinite text of King James Bible (followed by itself again and again forever).

Conclusion: if the digits of pi have any endless human meaning (and they really have), this does not surprise anybody.

HOOTmag (talk) 09:36, 20 September 2011 (UTC)

Back to the original question (I'm assuming the "string" found is mathematically very statistically significant in well formed english which I think was the intended question eg not just finding "Hello" in a random series of 4 billion digits..) (You'd have to eliminate the possibility that the structure of the language you were using wasn't susceptible to producing readable text from random digits etc) - I would expect that the mathematical community - like most other sentient beings would take it as proof that an influence external to the universe was leaving messages for us.. - (though a significant percentage of people's heads would explode with the significance of it all..)

Sherlock_Holmes#Holmesian_deduction has a good quote for this possibility "When you have eliminated the impossible, whatever remains, however improbable, must be the truth" . This hasn't happened yet right?Imgaril (talk) 10:36, 20 September 2011 (UTC)

September 20

When will Goldbach's conjecture be tested.

Since the "odds" of a Goldbach's conjecture violation are 10^-3700 (see page history for deleted post), when will it be tested up to 10^4000 to ensure that no counterexamples are found in the expected range? Hcobb (talk) 03:36, 20 September 2011 (UTC)

I don't think that will ever be possible, as that's way more than all the atoms in the universe. StuRat (talk) 04:19, 20 September 2011 (UTC)

That's not how it works. The figure of 10^-3700 is given for an even number of a specific magnitude, which as I understand is on the order of a few thousands. For larger numbers the probability is smaller. By the time you get to the even number 10000 the probability is maybe 10^-10000 (made up number) and so on. These very low probabilities mean the opposite of what you're implying - it means we're more confident of Goldbach's conjecture, not less confident and in need to look harder to be convinced. -- Meni Rosenfeld (talk) 07:41, 20 September 2011 (UTC)

Your first post [1] was removed because it didn't ask a question. Goldbach's comet says: "the probability of zero pairs for any one E, in the range considered here, is of order 10^-3700." The range in the graphs of the article is 1,160,000 to 1,540,000. My own calculations also indicate that for the middle of this range around 1,350,000 the odds are of order 10^-3700. Your question apparently assumes that the odds are the same for each even integer but in fact the odds decrease quickly when the integer grows. My quick estimate says the odds are 10^-15 for 1,000, 10^-75 for 10,000, 10^-440 for 100,000, 10^-2900 for 1,000,000, and 10^-20500 for 10,000,000. It is far smaller for numbers beyond the search limit of 26×10¹⁷ a week ago.[2] The sum of the odds taken over all numbers above 26×10¹⁷ is extremely small so we think Goldbach's conjecture is highly likely to be true. However, the calculation of the odds makes assumptions that seem reasonable and fits existing data very well but could theoretically turn out to be wrong. PrimeHunter (talk) 10:33, 20 September 2011 (UTC)

Even 10^10000 is only a ten thousand digit number and will handily fit in the CPU cache of any laptop. (It's a little more than 4KB.) So why not build a quantum prime solver of this modest size? (Assuming quantum computers actually work of course.) Hcobb (talk) 10:55, 20 September 2011 (UTC)

We don't have useful quantum computers and I don't know whether there is an algorithm which would aid Goldbach's conjecture significantly. If we could instantly determine whether a number is prime then the project reaching 26×10¹⁷ would still have to examine each even number and only become a little faster. By the way, existing computers and algorithms can handle individual numbers the size of 10¹⁰⁰⁰⁰ = 47717 + 10¹⁰⁰⁰⁰-47717. I just found the probable prime 10¹⁰⁰⁰⁰-47717 in 15 minutes on a PC. It is almost certainly prime but it would take much longer to prove primality. PrimeHunter (talk) 11:44, 20 September 2011 (UTC)

Intergrating ring of charge in 1/r field

Re #Distribution of charge in 1,2,3 dimensions on symmetrical bodies (second part) - I got stuck (no suprises there) - I was trying to sum (integrate) the combined effect of a ring (circle or radius r) of "charge" generating a 1/r field at distance r , at an offset f from the centre of the ring.

I got the integral between 0 and pi of (f-rcosθ)r/(f²+r²-2frcosθ) , which I boiled down to the integral of

1/2f (1 + (f2 - r2)/(f2+r2-2frcosθ) )

At which point I got stuck. Clues appreciated. Thanks. Imgaril (talk) 10:30, 20 September 2011 (UTC)

Laplacian correction for discriminative naive Bayes

In a naive Bayesian classifier with discriminative learning, is it appropriate to increase the amount of Laplacian correction with the logarithm of the dimensionality, as the Weka package DMNBtext does? If so, does this still hold as dimensions with less and less entropy (e.g. rare words being encountered for the first time) are added? I ask this because I'm testing a straight conversion of DMNBtext in a chat-spam filter, and finding that its probabilities are too close to 50% (i.e. it's not confident enough in its classifications). NeonMerlin 12:17, 20 September 2011 (UTC)

I don't know enough to give a straight answer, but maybe I can offer an opinion if you clarify the context and notation.

Do I understand correctly that DMNBtext assumes that in addition to the observed words, there are $\log(d)$ prior words divided evenly among the d words in the vocabulary, for each example? This does sound like a lot, especially if there aren't many real words in each example. I'm not sure about the theory that supports the logarithmic value, but it undoubtedly based on a specific prior on the distribution of word frequencies, which may not match the real distribution.

Also, why would it give 50% rather than whatever the prior class frequencies are?

AFAIK Naive Bayes is a generative model, what do you mean by using it in discriminative learning? -- Meni Rosenfeld (talk) 14:53, 20 September 2011 (UTC)

Is this function chaotic

I was interested in chaotic functions a while back, so I tried to make one. I think I may have stumbled on one that is chaotic, though I am not sure. Failed to parse (syntax error): {\displaystyle f(a,x) = a × \left ( \frac{x}{a} − 2 × \left \lfloor \frac{x}{2 × a} + \frac{1}{2} \right \rfloor \right ) × (-1)^{\left \lfloor \frac{x}{2 × a} + \frac{1}{2} \right \rfloor} g(x) = (\left \vert x \right \vert % 1) × {\left \lceil \left \vert x \right \vert \right \rceil} + 0.5 × {\left \lfloor \left \vert x \right \vert \right \rfloor}^2 + 0.5 × \left \lfloor \left \vert x \right \vert \right \rfloor \\ h(a,x)=f(a, \frac{g(x)}{f(a,x) + 1) }

--Melab±1 ☎ 20:01, 20 September 2011 (UTC)

Are the following formulas what you wanted? The formulas you typed above have syntax errors so they aren't showing up.

$f(a,x)=a\times \left({\frac {x}{a}}-2\times \left\lfloor {\frac {x}{2\times a}}+{\frac {1}{2}}\right\rfloor \right)\times (-1)^{\left\lfloor x/(2a)+1/2\right\rfloor },$

$g(x)=(\left\vert x\right\vert \%1)\times {\left\lceil \left\vert x\right\vert \right\rceil }+0.5\times {\left\lfloor \left\vert x\right\vert \right\rfloor }^{2}+0.5\times \left\lfloor \left\vert x\right\vert \right\rfloor ,$

$h(a,x)=f\left(a,{\frac {g(x)}{f(a,x)+1}}\right)$

Also, does the percent sign mean modulo?

– b_jonas 20:34, 20 September 2011 (UTC)

Knuth's The Art of Computer Programming chapter 3.1 concludes that you cannot generate random numbers using random methods, which I think might imply that this function is not chaotic. – b_jonas 10:06, 21 September 2011 (UTC)

Is there supposed to be a recurrence relation here? e.g. x(i)=h(a,x(i-1))

Yaris678 (talk) 12:43, 21 September 2011 (UTC)

Chaos theory deals with something quite different from noise though it may sometimes appear to be noise, an yes a recurrence relation would be a good idea for the question! It can be quite reasonable to say something exhibits both chaos and random noise. Dmcq (talk) 18:20, 21 September 2011 (UTC)

Who mentioned noise? Yaris678 (talk) 19:24, 21 September 2011 (UTC)

Above see b_jonas that I was replying to. Random means noise. Chaos isn't random. Dmcq (talk) 19:49, 21 September 2011 (UTC)

I think b_jonas meant pseudorandom. Pseudorandom number generators makes use of chaos to appear random. Yaris678 (talk) 21:01, 21 September 2011 (UTC)

Yes, those are what the equations were supposed to look like and the percent sign is modulo. There is no recursion. Just specify $a$ in $h(a,x)$ and $x$ is the input. --Melab±1 ☎ 20:43, 21 September 2011 (UTC)

September 21

Binary numbers with no adjacent 1s

I was calculating how many patterns there are for binary numbers of length L where there are never two adjacent 1s.
Thus L1 has 1 = 1
L2 has 01 and 10 = 2
L3 has 001 010 100 and 101 = 4
L4 has 0001 0010 0100 1000 0101 1010 1001 = 7.
Further terms are L5 = 12, L6 = 20, L7 = 33, L8 = 54, L9 = 88 etc.
It turns out that these are the fibonnaci numbers less one. Is there any reason why these are related to the fib nos, or is it just a big coincidence? -- SGBailey (talk) 15:15, 21 September 2011 (UTC)

They satisfy the Fibonacci recurrence. Count the number of admissible binary strings of length n, conditioned on whether the first digit is a 1 or 0. Sławomir Biały (talk) 15:27, 21 September 2011 (UTC)

Sorry - I don't understand what your reply says. Can expand or rephrase or something please. -- SGBailey (talk) 15:30, 21 September 2011 (UTC)

What makes it a little more consistent is that you are dropping the all zero case. Once you add that, you end up with a fairly easy construction. L(N) consists of all of the entries in L(N-1) with a 0 added at the front and all of the entries of L(N-2) with a 10 added at the front so L4 = 0/000 , 0/001, 0/010, 0/100, 0/101 and 10/00, 10/01, 10/10. (It works out the same with a 0 added at the end of the L(N-1) and a 01 added at the end of L(N-2))Naraht (talk) 15:35, 21 September 2011 (UTC)

Note that the string counts don't satisfy the Fibonacci recurrence - they satisfy

$x_{n}=x_{n-1}+x_{n-2}+1$

It just so happens that $x_{n}=F_{n}-1$ satisfies that recurrence too. Gandalf61 (talk) 15:38, 21 September 2011 (UTC)

Sorry, I didn't realize we were excluding the case of all zeros. The recurrence is easier to get if you don't artificially exclude this possibility. Sławomir Biały (talk) 16:03, 21 September 2011 (UTC)

It's sequence A000071 in the OEIS, if any of that gives you a lead. Grandiose (me, talk, contribs) 15:31, 21 September 2011 (UTC)

Makes sense now. Thanks. -- SGBailey (talk) 18:21, 21 September 2011 (UTC)

Mandatory link: Fibonacci coding. -- Meni Rosenfeld (talk) 07:45, 22 September 2011 (UTC)

eating mashed potatoes with your hands when silverware is available

Some (all?) computer programming languages required everything to be written using only characters on standard keyboards. One can write 3 x 4 (with the letter x as a substitute for ×) when one types a letter, but in programming languages one wants that letter to be available for other uses, so a workaround was adopted, the asterisk: 3 * 4.

But within Wikipedia there's a little menu from which one can chose the "×" character, and in TeX and LaTeX and the like one can write

$3\times 5,\qquad 3\cdot 5,\qquad 3\otimes 5,\qquad 3\boxtimes 5,\qquad 3\odot 5,$

etc., etc. There's no need for uncouth substitutes or workarounds.

But within Wikipedia and elsewhere, even today, one finds people eating mashed potatoes with their hands when silverware is available, writing

$3*5\,$

in TeX!

Are people being taught in school today that the use of the asterisk for this purpose is a standard thing rather than a substitute used in the remote wilderness when limited to keyboard characters? Michael Hardy (talk) 20:18, 21 September 2011 (UTC)

(I posted this to the language reference desk as well.) Michael Hardy (talk) 20:18, 21 September 2011 (UTC)

I don't think this is something that's taught as correct from a notational point of view, because, for example, I don't ever (well, hardly ever) see people use asterisks when they write math by hand. I think people just learn through experience with things like spreadsheets, programming languages, Texas Instruments calculators, and so on that the asterisk is the character that represents multiplication when dealing with computers, so they use it here too. On the other hand, I don't think I've ever been explicitly told by anyone that, in ordinary usage, the asterisk is not an acceptable substitute for a proper multiplication sign—I just had to infer that by reading a lot of math and noticing the symbols that were used. So the answer, I think, is that notation is rarely taught explicitly; everyone picks up notation by observing patterns in what everyone else uses, and some people don't notice (or haven't yet noticed) that the use of the asterisk is generally limited to certain contexts. —Bkell (talk) 22:18, 21 September 2011 (UTC)

Silverware is not always available. I can not write 3×5 cm² in an email. Editing wikipedia, after typing 3\times 5\,cm^2 you must type alt+shift+P in order to see the picture $3\times 5\,cm^{2}$, which is not silverware calligraphy anyway. Mathematics was written by hand by people who knew the greek alphabet, but now the notation is intimidating to young readers, and even computers do not understand it. The old mathematical notation must eventually be replaced by some programming language. Personally I like the J (programming language). The last word has probably not been said yet. Bo Jacoby (talk) 10:17, 22 September 2011 (UTC).

I don't understand what you mean by saying you need to type alt+shift+P to see $3\times 5\,cm^{2}$. On the machine I'm at, alt+shift+P is for "private browsing". I certainly don't need to do that in order to see $3\times 5\,cm^{2}$. Michael Hardy (talk) 22:14, 22 September 2011 (UTC)

I usually prefer that people write asterisks on computers so expressions can more easily be copy-pasted to a program or expression parser. I read some math mail lists and forums where it's possible to write × but nobody does it and it would be very annoying if they did. But in Wikipedia I write × in articles (not always in discussions). PrimeHunter (talk) 12:18, 22 September 2011 (UTC)

Does anyone commonly use × for multiplication past elementary school level math? In my own experience I would say no. It's too easy to confuse it with the letter x, even if you're using a type set that distinguishes them. If a student used × for multiplication, I would tell them not to. I don't think it's correct to assume that using × is the standard notation, since this seems to contradict the empirical evidence. Rckrone (talk) 19:38, 22 September 2011 (UTC)

You're quite mistaken. For one thing, it's used for the cross-product of vectors, and it's commonly used when writing about measurements or referring, for example, to an $n\times m$ matrix. It's also used for Cartesian products of sets and spaces and direct products of groups. It is used in some contexts when the only things one is multiplying are integers, e.g. when talking about prime factorizations of numbers. And sometimes it's used as the last character on a line when one wants to make it clear that the list of factors being multiplied continues on the next line. Michael Hardy (talk) 22:18, 22 September 2011 (UTC)

September 22

Mixed Member Proportional Voting and Gerrymandering

Because of overhang seats in some MMP systems, it it still possible to gerrymander the constituencies to take advantage of this effect to get a larger portion of seats for your party? Obviously the effect would not be as great as with FPTP, but is it still technically possible? --CGPGrey (talk) 07:45, 22 September 2011 (UTC)

I guess, but the effect (disproportionateness) is larger the less popular (in terms of party vote) a party is, and less popular parties don't have all that much opportunity to gerrymander, so in practical terms it doesn't mean much. However, if there is no threshold, then under the Sainte-Laguë method of apportioning seats, very small parties are able to gerrymander themselves by splitting into smaller parties. For example, in New Zealand at the last election, if there had been no threshold, a party would have been able to get in (with one MP) with something like 0.43% of the vote. If a party got 1% of the vote, they would also have gotten 1 MP (I think - I'll have to doublecheck that later on). If such a party split and ran as two independent parties, each attracting half of the original party's votes, then each would get 1 MP.