Wikipedia:Reference desk/Archives/Mathematics/2008 December 8

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 8

Infinite Box

Suppose you have a box with infinite volume. If you filled said box with an infinite amount of baseballs, would the box's volume be filled, even though the baseballs won't stack evenly and there will be space left inside? [[User:Shane 42]] (talk) 04:27, 8 December 2008 (UTC)

The space between the baseballs will still be there, so space is not filled, and no it is not possible to have infinite number of basballs. Graeme Bartlett (talk) 07:20, 8 December 2008 (UTC)

This question is strange but if you have a boX (my keys don’t work) of uncountable volume and only countably infinitely many balls, the anser (again my key does not work) is no because the countable union of finite sets is countable.

Topology Expert (talk) 09:08, 8 December 2008 (UTC)

But a baseball isn't a finite set, it contains an uncountable number of points. --Tango (talk) 13:18, 8 December 2008 (UTC)

Yes, but its measure is finite (forgive me for my mathematical language earlier; I am jut really annoyed with my keyboard). Topology Expert (talk) 14:44, 8 December 2008 (UTC)

I don't think the solution of the "paradox" can involve a countable/uncountable distinction because a countably infinite number of unit cubes would fill the box completely. I think you have to start with the finite case - a nxnxn box filled with unit spheres - and then find the limit of the proportion of the box's volume that is filled by the spheres as n tends to infinity. This is just over 74% for a regular close-packing arrangement, but empirical evidence suggests about 64% for a random arrangement - see sphere packing. Gandalf61 (talk) 11:55, 8 December 2008 (UTC)

Is there a sensible notion of volume that allows it to be uncountable? Algebraist 14:19, 8 December 2008 (UTC)

Well, you could bring measure theory into this. That would allow the volume to be uncountable. Topology Expert (talk) 14:44, 8 December 2008 (UTC)

In what sense? A measure is a real number, isn't it? Not a cardinal number. --Tango (talk) 15:40, 8 December 2008 (UTC)

I don't think "uncountable volume" has any meaning, even in the context of measure theory. The number of points in the set is uncountable, but that doesn't say anything about its volume. (There are uncountable sets with zero volume, others with positive but finite volume, and still others with infinite volume.) The volume is going to be a nonnegative extended real number, so there's only one type of infinity that's meaningful. —Bkell (talk) 15:43, 8 December 2008 (UTC)

I forgot the fourth possibility, of course, which is that there exist uncountable sets which are non-measurable and thus don't have any meaningful volume at all. —Bkell (talk) 15:46, 8 December 2008 (UTC)

I can't epre myelf becaue of my keyboard...

Top. EPERT

As to the last point (whether "uncountable volume" has any meaning in measure theory): it does not exist as a term, but the meaning here should be that of a measure space which is not sigma-finite. A measure space need not be sigma finite, that is, it need not be a countable union of sets of finite measure. A natural example is the p-dimensional Hausdorff measure in R^n, with p<n. In fact, from the axioms of measure it does not even follow that a measure be "regular at infinity": there could be a "heavy atom", that is, a measurable set of infinite measure containing no subset of finite and positive measure (I will not translate this into the example with baseballs and a box not regular at infinity). By the way, any measure can be decomposed into the sum of a measure regular at infinity plus one with only values 0 or infinity.--PMajer (talk) 15:23, 9 December 2008 (UTC)

Yes, that is what I should have said (I am a bit patchy with my measure theory definitions, you see). Maybe an easier example of a non-sigma finite measure space would be an uncountable set given the counting measure (the measure of a subset here is simply its size) (the Hausdorff measure also works and is definitely more natural in the sense that it has applications in many branches of mathematics but this is an easier to understand example). Topology Expert (talk) 09:00, 10 December 2008 (UTC)

Geeeeez.... again I'm surprised by the complexity of the answers. Suppose you number the spaces where basketballs potentially might fit: 1, 2, 3, 4, 5, .... Then put a basketball in every even-numbered space, leaving the odd-numbered spaces empty. Then you've put in infinitely many basketballs, but you haven't filled the space. Michael Hardy (talk) 01:10, 10 December 2008 (UTC)

In what sense have you then 'filled said box'? I would take that to at least require that there be no room for more basketballs. Algebraist 09:32, 10 December 2008 (UTC)

That's what I'd expect "filled" to mean. If you just want to fit an infinite number of balls in then you can just put them along one line, virtually all (not strictly "almost all") the box would then be empty. If you fill the box with balls then you will have an infinite number of balls, taking up an infinite amount of space, and you'll have an infinite amount of space left over between the balls. There is no problem with having an infinite proper subset of an infinite set, which is probably where the OP is getting confused. --Tango (talk) 14:17, 10 December 2008 (UTC)

You could do a similar sort of thing with half-boxes. Imagine a line, where a basketball fits snugly in 1 unit of space. You place a basketball between points 0&1, 1.5&2.5, ... (n*1.5)&(n*1.5+1). As there is only a half space between each basketball, there isn't room to put another 1-unit wide basketball between any two other basketballs. (Let's say you can't push the basketballs together due to constraints imposed in the other dimensions.) You now have an infinite number of basketballs which on their own take up an infinite amount of space, contained in a box of infinite space, and you still have an infinite amount of space left over. That is: "∞ - ∞*1 = ∞". That's the sort of weirdness you should expect when working with infinity. (Certainly you could have interpret "filled" to mean "no empty space left over", but I don't think that's what the questioner is after. My guess is that he wants confirmation that yes, you can put an infinite number of finite volume objects (totaling an infinite amount of volume) into an infinite box and still have room left over.) -- 128.104.112.113 (talk) 21:02, 11 December 2008 (UTC)

Elliptic Curve Cryptography Problem...

In ECC, why must each plaintext be transformed to (x,y)-point on a certain elliptic curve(i.e., plaintext embedding on EC)?

If we just use the plaintext point whether it is on EC or not, is there any problem in encryption and decryption in ECC? Please take a look at the example below:

Example)

y^2 = x^3 + x + 1, p = 23. We take the receiver's public key, {G = (0,1), p = 23, rG = 1(0,1) = (0,1)}.

Here, r = 1 is the receiver's private key.

We choose the plaintext M = (2,1) which is not on the EC.

The sender encrypts it using his private key, s = 2.

So, C1 = sG = 2(0,1) = (6,19) which is on EC, and C2 = srG + M = 2G + M =2(0,1) + (2,1) = (18,19) which is not on EC.

Now, let's decrypt it.

C2 - rC1 = (18,19) - 1(6,19) = (18,19) + (6,-19) = (18,19) + (6,4) = (2,1).

We got the right plaintext back here.

In this case, I do not see any problem. Do I misunderstand something here?

The purpose of having an elliptic curve in ECC is to provide a finite group with a (conjectured) hard discrete log problem. The group in this case is the rational points on an elliptic curve under "point addition". If you're not dealing with rational points on an elliptic curve, I wonder how you define the addition of two points. It is not necessary to encode the plaintext as point on the elliptic curve. If you're using an elliptic curve analog of Diffie-Hellman, you use the derived common secret to somehow generate a key, and use the key to encrypt your plaintext. There are many possible ways to do the key derivation and encryption. --98.114.146.75 (talk) 05:11, 10 December 2008 (UTC)

Agreeing with the previous poster, in something like IES, the elliptic curve part mostly stops at deriving a common secret. You choose s randomly every time you want to send a message and send sG to someone who published rG as his public key (because he knows r). Your shared secret is then rsG, which can be used in various ways to derive a key for some other encryption algorithm.

Your suggested encryption seems to be M -> (sG,rsG + M) for some fixed s. However, if someone can decrypt a single message, then they can recover rsG and then can decrypt all future messages ("known plaintext attack requiring 1 known plaintext"). This does not depend on M being on the curve. You need s to be chosen randomly (and hopefully co-prime to the order of G) for each message.

It might also be useful to compare to RSA. Here the group is the multiplicative group of units in Z/pqZ. Typically you send M^e mod pq where M is in the group. M does not have to be on the group to compute M^e of course. You could take M to be 0 for instance, then M^e would also be 0. The map M -> M^e is not only a bijection of the group, but also on all of Z/pqZ. However, it is only difficult to invert on the group. You should be careful then to check that not only does your new "encryption" not destroy the data, but that it is also difficult to decrypt without the key.

Looking at your scheme (assuming you choose s randomly), you are choosing the KDF "take the shared secret rsG and use rsG as the key" and the symmetric encryption "take the messsage and encode it as a point in the plane, and then somehow add the point rsG to it". Here the KDF is probably ok as it should be uniformly distributed in the key space (the points on the curve in the cyclic subgroup generated by G) and the EC discrete log problem is equivalent to deriving the secret key from the shared key, but people tend to use real KDF's for a reason. The symmetric encryption is probably not ok. I'll assume you have a well defined notion of addition (ec-point,plane-point) -> plane-point. So you have a group of order roughly q (the elliptic curve) acting on a set of order roughly q^2. Hence there are at least q orbits, and so the ciphertext specifies approximately half of the bits of the plaintext. JackSchmidt (talk) 07:40, 10 December 2008 (UTC)

In ECC, it is necessary to encode the plaintext as point on the elliptic curve. This is a principle in ECC, and I want to know any counter example againt my example.203.237.141.30 (talk)

Mallows' Cp

Does Mallows' Cp can just be applied to compare nested linear regressions? Re444 (talk) 09:52, 8 December 2008 (UTC)

I'm not sure I understand the question. But comparing nested linear regressions is the usual use of Mallows' C_p statistic. Michael Hardy (talk) 01:06, 10 December 2008 (UTC)

I've just seen a paper in which the applied criteria on the model selection process, were Mallows' Cp & F-test & AIC (and r^2), while none of the models were linear and not all of them nested. I know that F-test is just applicable to nested models, but I’m not sure about Cp. Is it a mistake using Cp in this situation? Re444 (talk) 17:16, 12 December 2008 (UTC)

Tax question

It is this time of year... While I do not want to know all the details or read all the relevant documents, may be there is relativly simple answer to my question. Given that I have short term and long term capital losses $L_{short},L_{long}$, as well as short term and long term gains $G_{short},G_{long}$, is there a simple algorithm how to calculate federal/state tax I owe in USA? I would appreciate if you send me in the right direction. A crude approximation will suffice, I am just trying to develop a stock trading/analyzing algorithm. (Igny (talk) 16:56, 8 December 2008 (UTC))

There is a lot of relevant information in our article on capital gains tax in the United States, including tables of rates and outlines of some deferment strategies. I understand you don't want to "know all the details or read all the relevant documents", but I doubt anyone is going to pre-digest this stuff for you for free. Gandalf61 (talk) 12:06, 9 December 2008 (UTC)

Crude approximation, no problem! Combine your four terms as follows:

• Combine all short-term gains and losses into one (signed) number; include a prior year short-term carryover here if you have one.
• Combine all long-term gains and losses into one number, including carryover. If you have them, add Capital Gains Distributions from mutual fund sales here also.
• Combine those two numbers. Schedule D still has more than half a page of computations from this point, but the simple-minded approach is: if this number is a gain, it's all taxable; if zero, it's zero; if a loss, there's a limit as to how much you can claim in a year.

Further calculations depend on whether your short net and long net are both gains, or one gain/one loss; whether or not you have qualified dividends; and other stuff well outside the bounds of Crude Approximation.

HTH, --DaHorsesMouth (talk) 00:22, 11 December 2008 (UTC)

Thanks, that is approximately what I was using so far. I just wondered how close was my approach to the reality. (Igny (talk) 02:48, 11 December 2008 (UTC))

Well-orderings of an aleph-1 set

I was reading the intriguing arguments for and against the axiom of constructibility (or any other axiom that implies the CH) here. However, I got stuck on the crucial part of the dart-throwing argument: that a well-ordering < on a set S with $|S|=\aleph _{1}$ can be constructed in such a way that for all $x_{0}\in S$, $\lbrace x\in S:x<x_{0}\rbrace$ is countable. To me, nowhere near a set theorist, this is hardly obvious. Any pointers? -- Jao (talk) 18:59, 8 December 2008 (UTC)

Well, $\aleph _{1}\,$ is usually defined as the cardinality of the set of all countable ordinals, so just look at that set in its usual ordering. The set is uncountable with cardinality $\aleph _{1}\,$, and each of its elements has only countably many predecessors. Michael Hardy (talk) 01:04, 10 December 2008 (UTC)

Assuming the axiom of choice, well order S, then consider the set T = { x in S : { y in S : y < x } is uncountable }. If T is empty, then the well-ordering used already works. If T is non-empty, then (since S is well-ordered) T contains a least element A. Then B = { y in S : y < A } is a an uncountable set since A is in T, but for any x in B, { y in B : y < x } = { y in S : y < x } is countable since x is less than A and so not in T. Since aleph1 is the least uncountable cardinal, and B has uncountable cardinality at most the cardinality of S, there is a f bijection of S and B. Define a new well-ordering on S by x < y if and only f(x) < f(y) in the old well-ordering. JackSchmidt (talk) 19:21, 8 December 2008 (UTC)

All right, I won't feel bad for not seeing that as obvious, but after reading through your proof (a couple of times) it's definitely clear. Thanks a lot! -- Jao (talk) 01:00, 9 December 2008 (UTC)

So the proof Jack gives is fine, but I'd just like to point out that you don't have to assume that S can be wellordered, or rather you've already assumed it, when you assumed that its cardinality was $\aleph _{1}$. That assumption means precisely that S can be put into one-one correspondence with the set of all countable ordinals, and those are wellordered by construction. --Trovatore (talk) 01:16, 9 December 2008 (UTC)

And for that matter, this also gives you the ordering you were looking for, the one where every proper initial segment is countable. --Trovatore (talk) 01:19, 9 December 2008 (UTC)

I knew this question would have me say it eventually, so here it comes: Duh. Thanks go out in equal measure to you. -- Jao (talk) 01:28, 9 December 2008 (UTC)

This is a very important set and has several applications in set theory and in fact mathematics in general (topologists use this set in-order-to construct the long line). Topology Expert (talk) 11:00, 9 December 2008 (UTC)

Jack's proof is the most reasonably obvious proof of this fact but it also assumes that given any uncountable set, there exists a well-ordering on that set. This is still disputed because for particular cases, no such well-ordering has been found (like for the countable product of the integers with itself). Topology Expert (talk) 11:00, 9 December 2008 (UTC)

Do you really need the AC? For $\aleph _{1}$ is just by definition the cardinality of $\omega _{1}$, which enjoys the property quoted in Jao's question. Ops I see that this has already remarked by Trovatore.--PMajer (talk) 14:44, 9 December 2008 (UTC)

No-one has found a well-ordering for the product of countably many copies of the integers? (I assume that's what you mean by "countable product".) Can't you use the standard function that proves the integers are countable to transform it into the product of countably many copies of the natural numbers and then use the lexicographic ordering? Maybe I'm just unimaginative, but I can't think of a set without a least element under that ordering. --Tango (talk) 15:52, 9 December 2008 (UTC) Oh, yes I can... --Tango (talk) 15:53, 9 December 2008 (UTC)

I believe he means the set $\prod _{n\in \mathbb {N} }\mathbb {Z}$, aka the continuum. This is not provably wellorderable in ZF (assuming as ever that ZF is consistent), though it is (slightly) misleading to say no well-ordering has been found; there is, for example, a formula which, under the assumption V=L, wellorders this set. Algebraist 16:00, 9 December 2008 (UTC)

Yes, you can assume and prove but you can't prove without assuming.

Topology Expert (talk) 17:08, 9 December 2008 (UTC)

Mapping circle to heart shape curve and cardioid

Hi. It is possible to map circle to cardioid using map :

$g_{1}(w)=w-w^{2}\,$

where w is a point or circle.

What equations has a map which converts circle to non-cardioid heart shape curve on this image ?

--Adam majewski (talk) 19:48, 8 December 2008 (UTC)

It's not complex-analytic, but $(x,y)\mapsto (x,{\sqrt {|x|}}-y)$ makes nice-looking heart shapes out of circles centered on the origin (different for different radii). -- BenRG (talk) 11:34, 9 December 2008 (UTC)

Thx. It works. I have made an image. There are 4 ( 2x2) points where lines seems to be "broken" ( not smooth) --Adam majewski (talk) 17:08, 9 December 2008 (UTC)

You are just plotting with too few points. 130.237.3.196 (talk) 17:52, 9 December 2008 (UTC)

I have tested with 1000 points and ... you are right. (:-) Can you explain it ? I will upload new image . --Adam majewski (talk) 20:43, 9 December 2008 (UTC)

It's not likely to be smooth everywhere, considering there is a |x| in it - the sharp points on the x=0 line are probably genuine singularities. --Tango (talk) 18:25, 9 December 2008 (UTC)

The image is very beautiful. The book is a Polish-Russian dictionary (isn't it?); is that page just random or has it a particular meaning? --PMajer (talk) 19:29, 9 December 2008 (UTC)

I will ask author. ( Please look at commans page, there is link to similar image ). --Adam majewski (talk) 20:43, 9 December 2008 (UTC)

Sorry, I didn't find the link you mentioned... where is it? Still compliments to the author. Beautiful and joyful way of expriming love and constancy to the study. The hart-shaped shadow camps there like a spiritual projection, on the apparently arid place of the dayly, hard intellectual work. The golden ring arises, hieratic, and shines like a candle; it really refers to another dimension. It put me of great mood.--PMajer (talk) 16:37, 10 December 2008 (UTC)

There's a link to Image:2006-12-03 Ring of love Edit.jpg from the image page. Algebraist 20:10, 10 December 2008 (UTC)