Testwiki:Reference desk/Archives/Mathematics/2010 May 2

{| width = "100%"

|- ! colspan="3" align="center" | Mathematics desk |- ! width="20%" align="left" | < May 1 ! width="25%" align="center"|<< Apr | May | Jun >> ! width="20%" align="right" |Current desk > |}

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

May 2

Information theory terminology

The entropy of a probability distribution $p$ over a discrete random variable $X$ is $\sum _{i=1}^n-p(x_i)\log p(x_i)$. I'm trying to find out what I should call one term of this sum. For example, what is $-p(x_i)\log p(x_i)$ called for $x_i$? It's not $x_i$'s surprisal, because that's $-\log p(x_i)$. Thanks. --Bkkbrad (talk) 01:10, 2 May 2010 (UTC)

The entropy contribution from $x_i$, or the mean surprisal of $x_i$ ? Bo Jacoby (talk) 06:02, 2 May 2010 (UTC).

Winning games

Where can I find a list of just the winning games in TicTacToe, preferably with each move displayed in the format of the game? 71.100.1.71 (talk) 15:30, 2 May 2010 (UTC)

The Tic-tac-toe article states that "When winning combinations are considered, there are 255,168 possible games." hydnjo (talk) 15:52, 2 May 2010 (UTC)

My expectation is that these would be computer generated and each game might consist of a row of 9, 0-2 values for each move for a maximum of 81 characters per game. That is a file of only 20 megs - well within the reach of even older personal computers. 71.100.1.71 (talk) 16:57, 2 May 2010 (UTC)

I don't think the number is anywhere near that large if you mod out by symmetries. Michael Hardy (talk) 19:07, 2 May 2010 (UTC)

Where can I find a list of just the winning games in TicTacToe, preferably with each move displayed in the format of the game? 71.100.1.71 (talk) 15:30, 2 May 2010 (UTC)

Copying your question verbatim is rude and isn't going to help. The question is a bit vague, you should elaborate on it. -- Meni Rosenfeld (talk) 08:37, 3 May 2010 (UTC)

Check this [1], for a close problem. --pma 17:22, 3 May 2010 (UTC)

There's an interesting discussion there, and even a link to yet another discussion! I'll go check that one out...

Error: Stack overflow. Suspect an infinite recursion.

-- Meni Rosenfeld (talk) 17:56, 3 May 2010 (UTC)

Shared Zeros of Quadratic forms

Hi there everyone,

I was hoping you could point me in the right direction on this one - it's for revision purposes so I certainly don't want the final solution, so please don't overhelp! :)

Suppose now that k = C and that $q_1,...,q_d:{ℂ}^n\to ℂ$ are quadratic forms. If n$\ge 2^d$, show that there is some non-zero $x\in {ℂ}^n$ such that $q_1(x)=...=q_d(x)=0$

I've already shown that there is a basis $\{v_1,...,v_n\}$ for $k^n$ such that, writing $x=x_1{v}_1+...+x_n{v}_n$, we have $q(x)=a_1{x}_1^2+...+a_n{x}_n^2$ for some scalars $a_1,...,a_n\in \{-1,0,1\}$. The 2^n makes me think of some sort of loose relation to binary (in terms of maybe having two 'options' for something n times) and the whole problem makes me think of induction, on d perhaps. However, I'm unsure how to actually formulate an approach to the program, and inductively whilst I've looked at things like defining $x_j$ such that $\mathrm{\forall }1\le i\le n,i\ne j,q_i(x_j)=0$ for $1\le j\le n$, but even if that is the right approach I'm not sure where to go from here inductively.

Many thanks for any help or advice you can provide! Simba31415 (talk) 18:58, 2 May 2010 (UTC)

Here are some hints. The key point is: the zero-set of a quadratic form q on Cⁿ contains a linear subspace W of dimension at least $\lfloor n/2\rfloor .$ (A linear subspace W contained in the zero-set of q is called a "totally isotropic subspace" for q). You can easily prove it using the normal form you wrote (for example, x²+y² on C² vanishes on the complex line of vectors of the form (x,ix) and so on). That said, prove the claim by induction on d. If d=0 there is nothing to prove: a system of no equation on Cⁿ with n≥2⁰=1 certainly has a non-zero linear space of solutions. Assume the claim is true for systems of d quadratic equations on Cⁿ when n≥2^d. Consider then a system of d+1 quadratic equations on Cⁿ with n≥2^d+1. Apply the induction hypothesis to the first d quadratic forms restricted on a totally isotropic subspace of dimension $\lfloor n/2\rfloor$ for the last quadratic form. Note that $\lfloor n/2\rfloor \ge 2^d$ because n≥2^d+1. --pma 14:45, 3 May 2010 (UTC)

Ideals in a PID

How would I go about showing that for ideals I = Ra, J = Rb in a PID, R, IJ = I $\cap$ J if and only if I + J = R? I can only seem to get so far with either implication. IJ is always contained in the intersection, so I've tried taking an x which is in both I and J, and showing I can write it as x = r(ab) for some r in R...with limited success. I tried toying with the idea of writing 1 = sa + tb (s, t in R), but couldn't get the expression in a helpful form. The result is easily true if I = R or J = R, so we can assume I and J contain no units, but I'm struggling to cobble all these facts together into a useful argument. Help is appreciated! Icthyos (talk) 22:01, 2 May 2010 (UTC)

You have x in I∩J, so x=ra=sb for r,s in R. Also, 1=ta+ub for t and u in R. Thus s=sta+sub, and so since a divides the RHS it also divides s, so x=sb=vab for v in R, and x is in IJ as desired. This is essentially the same proof as in the special case R=Z, with a and b being coprime (Za+Zb=Z being the coprimality assumption). Algebraist 22:50, 2 May 2010 (UTC)

In fact, you can prove both implications at once and more besides by showing that ab=gcd(a,b)*lcm(a,b) (up to associates). This works since Ra∩Rb=Rlcm(a,b), while Ra+Rb=Rgcd(a,b). Algebraist 23:00, 2 May 2010 (UTC)

A-ha, thanks - I had a feeling it would be something to do with writing 1 like that. How do you go about defining gcd and lcm for a general (not necessarily ordered?) PID though, or were you just referring to the case R = Z in your second comment? Thanks, Icthyos (talk) 11:26, 3 May 2010 (UTC)

You define GCD the same way you do (or at least should) in Z, or in any commutative ring for that matter: gcd(a,b) is a largest common divisor of a and b, with "largest" being interpreted in the divisibility order (a≤b iff a divides b). Thus a gcd is a common divisor which is divisible by all other common divisors. This means of course that the gcd is only defined up to associates. Algebraist 11:43, 3 May 2010 (UTC)

Ah, right. That makes a lot of sense. Thanks again! Icthyos (talk) 14:52, 3 May 2010 (UTC)