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

October 27

Is there an Erdős–Ko–Rado theorem for binary codes?

Hello,

I read Erdős–Ko–Rado theorem and I was thinking about alternative forms of this theorem. For binary codes of length $n$, I was thinking of a theorem like this: let $S$ be a set of binary codewords of length n, all being equal in at least one position. Then $|S|\leq 2^{n-1}$ and the bound can only be reached by taking all $2^{n-1}$ codewords with some fixed value in some position.

However, that turns out to be wrong, because for $n=3$, I can take $(0,0,0),(0,0,1),(0,1,0),(0,1,1)$ but also $(0,0,0),(1,0,0),(0,1,0),(0,0,1)$.

In fact, if the length $n$ is odd, I can always do that: I take one codeword, and switch in less than half of the positions, and I will get exactly $2^{n-1}$ codewords, all agreeing in at least one position.

Perhaps this is a very hard and open problem. I was just wondering if this problem has already been considered. Many thanks! —Preceding unsigned comment added by User:Evilbu (talk • contribs)

Okay, so you are asking if S is a set of binary codewords of length n, and each pair of codewords in S are equal in at least one position, then can we prove that $|S|\leq 2^{n-1}$, and when is equality reached ? Well, if s is a binary codeword then the only binary codeword of the same length that does not equal s in at least one position is the binary complement of s. So if we partition the binary codewords of length n into 2^n-1 pairs, each pair containing a codeword and its binary complement, then we can choose one codeword from each pair to give a qualifying set S with 2^n-1 members, and indeed there are 2^{2^{n-1}} ways to do this. But if we have a set with more than 2^n-1 members then, by the pigeonhole principle, it must contain at least one pair of complementary codewords, and this pair is not equal in any position.

For example, if n=3, we can choose either (0,0,0) or (1,1,1); either (1,0,0) or (0,1,1); either (0,1,0) or (1,0,1); and either (0,0,1) or (1,1,0), giving 16 ways of constructing a set S with 4 members. Gandalf61 (talk) 10:50, 27 October 2009 (UTC)

Or in other words : the entire set of codewords just falls apart into pairs, and I just have to take one from each pair. Okay, that's perfectly obvious now, I should have seen that. Thanks a lot! —Preceding unsigned comment added by User:Evilbu (talk • contribs)

Calculating a chord of a sphere

So for amusement, because it's too "early" to go to bed (long story), I'm trying to calculate how far it is from Portland, OR (USA) to Hyderabad (India), and I'm a little stumped as to how to do it. The chord article gives how to calculate the distance between two points in a circle, though calculating theta to plug into that equation is also not trivial (well, for me, I'm not much of a math person). SDY (talk) 12:11, 27 October 2009 (UTC)

You may be interested in this filed thread. The article great circle distance may be the most direct article to start reading. Well, you may well be slept by now. Or awake. Whatever... Pallida  Mors 14:44, 27 October 2009 (UTC)

Once you've realized how to do it, it is quite simple even starting from the fundamental principles, if you assume a spherical Earth with radius r. I assume you know the latitude φ and longitude λ of the places. Triples (r, φ, λ) are vectors in spherical coordinates from the center of Earth to the places, and their scalar product, which can be most easily calculated by first converting the vectors to cartesian coordinates (see this), is, on the other hand, r² cos α, where α is the angle between the two vectors. Finally, αr is the great circle distance sought for. — Pt _(T) 18:17, 27 October 2009 (UTC)

If you are actually looking for the chord length (sorry about my absent-mindedness), then the cos θ that goes into the formulae for chords is just my cos α. — Pt _(T) 18:23, 27 October 2009 (UTC)

I thought a chord meant a straight line (through the earth) between the two points, not an arc (great circle) on the earth's surface. Anyway, same idea. Calculate the rectangular coordinates of both points, then use the Pythagorean distance formula. 69.228.171.150 (talk) 06:41, 28 October 2009 (UTC)

Irrational exponents

A question about exponentiation:

We all know what a rational exponent is. But what about irrational exponents? I can't seem to find a definition anywhere? For example, in 2^π, do we take rational numbers approaching pi, put them into the function 2^x, and find the limit of 2^x as x approaches pi? ²³¹₉₁Pa (talk) 12:45, 27 October 2009 (UTC)

An irrational power of a positive real number can be defined by a limit process, as you suggest. Alternatively, once you have defined the exponential and logarithm functions, then you can use $b^{x}=\exp(x\ln(b))$ as a definition. See Exponentiation#Real powers. Gandalf61 (talk) 12:53, 27 October 2009 (UTC)

It's dealt with in Walter Rudin's Principles of Mathematical Analysis. Michael Hardy (talk) 14:41, 27 October 2009 (UTC)

Intuitively you can think of exponentiation with an irrational exponent as a limit process like that. In calculus, arbitrary powers are usually instead defined in terms of exponentiation, so $2^{\pi }=\exp(\pi \cdot \log 2)$, and exponentiation is defined as the inverse of the logarithm, where the log is defined as an integral (a different sort of limit process): $\log x=\int _{1}^{x}{1 \over x}\,dx$ —Preceding unsigned comment added by 69.228.171.150 (talk) 17:34, 27 October 2009 (UTC)

Power set of a Cartesian product

Is ${\mathcal {P}}(X\times Y)={\mathcal {P}}(X)\times {\mathcal {P}}(Y)$? --88.78.239.155 (talk) 14:07, 27 October 2009 (UTC)

No. There are lots of subsets of $X\times Y$ not of the form $A\times B$ for $A\subset X,B\subset Y$. Try an example where X and Y have size 2. Tinfoilcat (talk) 14:16, 27 October 2009 (UTC)

(after edit conflict) No. The members of ${\mathcal {P}}(X\times Y)$ are sets of pairs, whereas the members of ${\mathcal {P}}(X)\times {\mathcal {P}}(Y)$ are pairs of sets. For example, if X={a} and Y={b} then X x Y = {(a,b)} and the members of P(XxY) are the empty set and {(a,b)} whereas the members of P(X)xP(Y) are (empty set, empty set), ({a}, empty set), (empty set, {b}) and ({a}, {b}). Gandalf61 (talk) 14:19, 27 October 2009 (UTC)

...and just look at the closed unit disk in the plane. It's doesn't look anything like the Cartesian product of two subsets of the line: it's not a rectangle. Michael Hardy (talk) 14:22, 27 October 2009 (UTC)

Is ${\mathcal {P}}(X\times Y)\subseteq {\mathcal {P}}(X)\times {\mathcal {P}}(Y)$? --88.78.239.155 (talk) 14:23, 27 October 2009 (UTC)

Is ${\mathcal {P}}(X\times Y)\supseteq {\mathcal {P}}(X)\times {\mathcal {P}}(Y)$? --88.78.239.155 (talk) 14:24, 27 October 2009 (UTC)

You can work that out by considering the definitions of the sets on each side of the $\subseteq$ sign, as indicated by the comments above. Short, factual questions such as these, with no context, have the appearance of homework problems. — Carl (CBM · talk) 14:34, 27 October 2009 (UTC)

(ec) If you read the above answers carefully, they should settle these questions too. Also, take into account the cardinality of the power set of X. However, notice that you may make the identification ${\mathcal {P}}(X\sqcup Y)={\mathcal {P}}(X)\times {\mathcal {P}}(Y),$ where $X\sqcup Y$ denotes the disjoint union of X and Y, in the obvious sense that each subset of the disjoint union of X and Y is uniquely the disjoint union of a subset of X and a subset of Y. --pma (talk) 14:42, 27 October 2009 (UTC)

What is ${\mathcal {P}}(\{a,b\})\times {\mathcal {P}}(\{c,d\})$? --88.77.252.209 (talk) 14:54, 27 October 2009 (UTC)

P({a,b}) has four members; P({c,d}) has four members; so P({a,b}) x P({c,d}) has sixteen members, each of which is an ordered pair consisting of a subset of {a,b} and a subset of {c,d}. I suggest you list them, then compare them with the sixteen members of P({a,b} x {c,d}). Gandalf61 (talk) 15:02, 27 October 2009 (UTC)

If you know what power sets and Cartesian products are then you can work that our for yourself. If you don't, then what are you doing asking so many questions about that? --Tango (talk) 15:31, 27 October 2009 (UTC)

I agree. We should not be required to answer further questions you pose unless you show us that you understand what you are asking. Mathematics is not simply a list of factual information tied together; one must make connections between different concepts. In this case, it would be of use to establish connections between these various notions. Reading the article power set may be helpful. --PST 07:07, 28 October 2009 (UTC)

Is ${\mathcal {P}}(X\times Y)\cap ({\mathcal {P}}(X)\times {\mathcal {P}}(Y))=\varnothing$? --88.78.15.156 (talk) 15:42, 28 October 2009 (UTC)

Yes. As you were told above, the LHS contains sets of pairs, the RHS contains pairs of sets. They are different things. --Tango (talk) 16:30, 28 October 2009 (UTC)

If you encode pairs as sets, the two concepts might collide. If $(x,y)=\{x,\{x,y\}\}$, consider $a=(\varnothing ,\varnothing ),b=\{a,\varnothing \},X=\{\varnothing ,a,\{\varnothing \}\},Y=\{\varnothing ,a\}$. Then I think the intersection includes $(a,b)$. -- Meni Rosenfeld (talk) 20:42, 28 October 2009 (UTC)

BMO-style question (ish) on sums & products

Hi all -

my friend asked me to help him with this question in his work earlier today and I confess it is bugging me to death, I'm not sure how to approach it at all.

Given real numbers $a_{1},..,a_{n}$, s.t. $\sum _{i}a_{i}=0$ & $\sum _{i}a_{i}^{2}=1$, what is the maximum possible value of $a_{1}a_{2}+a_{2}a_{3}+...a_{n}a_{1}$? By considering the dot product of $(a_{1},..,a_{n})$ and $(a_{2},..,a_{n},a_{1})$ I can see such a sum must $\leq 1$, but I can't see any such $a_{i}$ which would actually make it equal to 1. Can anyone suggest a method to solve this problem?

Thanks a lot Mathmos6 (talk) 16:32, 27 October 2009 (UTC)

That does sound like a homework problem. Consider that the numbers don't all have to be positive. 69.228.171.150 (talk) 17:41, 27 October 2009 (UTC)

I doubt the OP imagined that the numbers are all positive and yet add up to 0. -- Meni Rosenfeld (talk) 19:46, 27 October 2009 (UTC)

Hints. You have a quadratic form $\textstyle (Ax\cdot x)$ in $\textstyle \mathbb {R} ^{n}$, represented by the symmetric matrix $A$ of order n, whose entries $\textstyle a_{i,j}$ are $1/2$ iff $\textstyle i-j=\pm 1\mod n,$ and $0$ otherwise.

Note that the hyperplane $\textstyle \{x\in \mathbb {R} ^{n}\,:\sum _{i=1}^{n}x_{i}=0\}$ is the orthogonal of the vector $u:=(1,1,..,1)$, which is the eigenvector of A corresponding to the maximum eigenvalue 1.

Therefore, your maximum is the second eigenvalue of A (in decreasing order).

Does this make sense to you?--pma (talk) 18:09, 27 October 2009 (UTC)

Is there a nice way to express the solution in the general case?

If anyone's interested, for $n=2,3,4,5,6,7$ the solutions are $-1,{\frac {-1}{2}},0,{\frac {-1+{\sqrt {5}}}{4}},{\frac {1}{2}},0.62348...$. -- Meni Rosenfeld (talk) 19:46, 27 October 2009 (UTC)

I think you skipped n=6 and I took the liberty of inserting it. For n=8 should be $\scriptstyle {\sqrt {2}}/2$... In fact if we work a bit on P_n(x):=2ⁿdet(x+A_n) we find a recurrence saying that P_n(x)/2=T_n(x)-(-1)ⁿ, whence we get all the eigenvalues of A_n using the T_n(cosθ)=cos(nθ).... but the OP and his friend already left... and these computations will be lost in time, like tears in the rain --pma (talk) 22:52, 27 October 2009 (UTC)

I follow all that, yes, so you end up with a very-nearly-tridiagonal matrix for A and you want the second largest eigenvalue - is there a nice way to evaluate det(A-tI) for a general n? Also, does this mean I was wrong about 1 being the maximum value for the sum, since you have eigenvalues greater than 1? Mathmos6 (talk) 23:28, 27 October 2009 (UTC)

Oh, apologies, I see you already said something about that (and I didn't leave, the wireless in my accommodation just broke for the day, just got it back on! :)) - I'm probably being stupid but what does T_n refer to, sorry? And where does my argument about the sum <= 1 fail? Thanks all for the help! Mathmos6 (talk) 23:30, 27 October 2009 (UTC)

well, if A_n were really tridiagonal, that is, if you remove the two 1's in the corners (1,n) and (n,1) (call the resulting tridiagonal matrix B_n), and you expand in the first column, you find a recurrence for det(B_n-tI) giving rise essentially to the Chebyshev polynomials of the second kind, U_n. The A_n have these two more 1's, but you can write det(A_n-tI) in terms of det(B_n-tI), using the linearity on the rows. A relation that you may find useful is U_n -U_n-2=2T_n, and you end up with the relation I wrote (I fixed it). Ask for details in case! cheers --pma (talk) 00:02, 28 October 2009 (UTC)PS: no, you were right: 1 is the maximum eigenvalue of A (the initial matrix with 1/2 and 0) but I think Meni used 2A to get rid of the factor 1/2. I think I used the initial A, but you better check...--pma (talk) 00:13, 28 October 2009 (UTC)

Exactly, I forgot to do the translation halfway through. Sorry for the confusion this has caused. I've fixed it now. -- Meni Rosenfeld (talk) 05:40, 28 October 2009 (UTC)

I think the eigenvalues are cos(2πi/n) with 0 ≤ i < n, so the largest less than 1 is cos(2π/n). If C is the transformation that shifts all the coordinates down one, then C has eigenvalues e^2πi/n. A = (C + C^-1)/2 so it has the same eigenvectors, and the eigenvalues would be (e^2πi/n + e^-2πi/n)/2 = cos(2πi/n). Does that seem correct? Is that what pma already said? I can't really tell. Rckrone (talk) 00:16, 28 October 2009 (UTC)

It seems so... what I found is that the eigenvalues of A_n are the roots of T_n(-x)=(-1)ⁿ --pma (talk) 00:36, 28 October 2009 (UTC)...that is of course the roots of T_n(x)=1 (that are exactly the cos(2πk/n), from T_n(cosθ)=cos(nθ) ). Rckrone's idea of using the (finite dimensional) spectral mapping theorem is definitely better to compute the spectrum of A--pma (talk) 00:46, 28 October 2009 (UTC)

This has been a great help, thankyou very much everyone! Think I've got my head around things now :) Cheers! Mathmos6 (talk) 00:45, 29 October 2009 (UTC)

Any method for solving the following equation...

Given the non-zero parameters: $a_{i},b_{i}$ (for every 1≤ i ≤6), is there any general method for solving the following equation:

$\sum _{i=1}^{3}{\sqrt {a_{i}x+b_{i}}}=\sum _{i=4}^{6}{\sqrt {a_{i}x+b_{i}}}$

HOOTmag (talk) 19:43, 27 October 2009 (UTC)

I think there isn't. Of course, you can find a solution numerically. -- Meni Rosenfeld (talk) 19:51, 27 October 2009 (UTC)

Is there any mathematical discipline dealing with related questions? HOOTmag (talk) 20:32, 27 October 2009 (UTC)

The general method would be to keep isolating one square-root term on the left-hand side and squaring out. You will eventually end up with a (large degree) polynomial, which can be tackled using the usual techniques (e.g. with Newton's method). You will have to check any solutions against the original, since the squaring operation can introduce roots. Zunaid 20:47, 27 October 2009 (UTC)

How can you be sure, this process "to keep isolating one square-root term on the left-hand side and squaring out...will eventually end up with a...polynomial"? HOOTmag (talk) 21:13, 27 October 2009 (UTC)

It's east to find the derivative of $\sum _{i=4}^{6}{\sqrt {a_{i}x+b_{i}}}-\sum _{i=1}^{3}{\sqrt {a_{i}x+b_{i}}}$ do just use Newtons method directly. Taemyr (talk) 21:36, 27 October 2009 (UTC)

I'm looking for an algebraic method. Sorry if this wasn't clear enough.HOOTmag (talk) 09:02, 28 October 2009 (UTC)

This doesn't work when you have more than 4 terms. In particular, if you put 5 square roots in one side and square them, you end up with 10 square roots.

Even if this was possible - if you want to use Newton's method anyway, why do the squaring in the first place? -- Meni Rosenfeld (talk) 21:21, 27 October 2009 (UTC)

Ah, I overlooked that. So it's not as trivial as simply squaring out to end up with a polynomial. To HOOTmag, there is (most likely) no algebraic solution to this problem, (probably) in the same way that there are no general algebraic solutions to polynomials of degree 5 or higher. Zunaid 09:27, 28 October 2009 (UTC)

I'm not sure it's "in the same way" (as you've put it), because solving quintic equations may have some method, in some (rare) cases, e.g. in quintic equations of the form: $(ax+b)^{5}=c$ (when given the non-zero parameters: a,b,c), etc. However I can't think of any equation of the form: $\sum _{i=1}^{3}{\sqrt {a_{i}x+b_{i}}}=\sum _{i=4}^{6}{\sqrt {a_{i}x+b_{i}}}$ (when for every 1≤ i ≤6 one is given the non-zero parameters: $a_{i},b_{i}$, such that every 1≤ j ≤6, not equal to i, satisfies: ${\frac {b_{j}}{a_{j}}}\neq {\frac {b_{i}}{a_{i}}}$), which may have - in some (even rare) cases - any method for solving that equation. HOOTmag (talk) 14:13, 28 October 2009 (UTC)

By my calculations, when you expand out the equation into a polynomial you get a degree 16 equation. A degree 16 equation isn't solvable in general but it may be that it's a special form that is solvable. I don't have a solution at the moment but I haven't seen anything to show it's impossible.--RDBury (talk) 16:02, 28 October 2009 (UTC)

How exactly do you expand out the equation into a polynomial? -- Meni Rosenfeld (talk) 20:12, 28 October 2009 (UTC)

I really don't know how you got a degree 16 equation. By my calculation, you'll never be able to get to any algebraic eqaution. HOOTmag (talk) 20:21, 28 October 2009 (UTC)

Yes, you can get a polynomial equation of which the original equation is a factor, by using Galois theory. We start with $\left(\sum _{i=1}^{3}{\sqrt {a_{i}x+b_{i}}}-\sum _{i=4}^{6}{\sqrt {a_{i}x+b_{i}}}\right)=0$

Each square root term is in a degree two extension of the polynomial ring in $x$. That means, $Y={\sqrt {a_{i}x+b_{i}}}$ is a root of $Y^{2}-(a_{i}x+b_{i})=0$. Since we have six square root terms in the original equation, it is in a degree $2^{6}=64$ extension of the polynomial ring in $x$.

To get a polynomial in $x$, we should multiply your expression by each of its conjugates-- each term ${\sqrt {a_{i}x+b_{i}}}$ is algebraic over the polynomial ring in $x$ and has the conjugate $-{\sqrt {a_{i}x+b_{i}}}$, which is the other solution to $Y^{2}-(a_{i}x+b_{i})=0$. (This is essentially the same trick as multiplying by the conjugate to rationalize the denominator in an expression like ${\frac {3}{2+{\sqrt {7}}}}$. In this case, we have 63 conjugates, since we are in a degree 64 extension.)

So, we need to multiply together all 64 terms of the form $\left(\pm {\sqrt {a_{1}x+b_{1}}}\pm {\sqrt {a_{2}x+b_{2}}}\pm \ldots \pm {\sqrt {a_{6}x+b_{6}}}\right)$, and the result will be a polynomial in x, with coefficients determined by the $a_{i}$ and $b_{i}$. I don't think it will be an easy equation to work with-- it will be a degree 32 polynomial. (In this case, we can obtain RDBury's degree 16 polynomial by omitting the first $\pm$, that is, only taking the 32 expressions with ${\sqrt {a_{1}x+b_{1}}}$ the positive square root. In general, though, we must multiply an expression by all of its conjugates to get a result in the base ring.)

Any solution to your equation will be a root of this polynomial (roots will be complex numbers in general), but most of the roots will be solutions to some conjugate of your equation; and I think it is possible that your equation has no solution. 140.114.81.57 (talk) 01:36, 29 October 2009 (UTC

That's pretty much the argument I had in mind but you don't really need the plus/minus in front of the first term. You can pair off factors in the form ${\sqrt {a_{1}x+b_{1}}}+Y_{1}$ with ${\sqrt {a_{1}x+b_{1}}}-Y_{1}$. So the product only needs 32 factors and the degree of the equation is 16. Not that it makes a difference, once you get a degree over 4 it's not solvable in general. But without knowing the Galois group, it might be a 2-group in which case you'd be possible to solve it with square roots.--RDBury (talk) 13:02, 29 October 2009 (UTC)

(after edit conflict). Substitute $y_{i}^{2}=a_{i}x+b_{i}$ to get 7 algebraic equations in the 7 unknown variables $x,~y_{i}$:

$y_{1}+y_{2}+y_{3}-y_{4}-y_{5}-y_{6}=0\,$

$a_{i}x+b_{i}-y_{i}^{2}=0\quad (i=1\cdots 6)$

Eliminate the 6 y's, using Buchberger's algorithm if everything else fails. The result is a polynomial equation in x alone. This concludes the algebra. The rest is numerical analysis. Bo Jacoby (talk) 02:00, 29 October 2009 (UTC).