Mathematics desk
< May 1	<< Apr \| May \| Jun >>	May 3 >

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.

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)[reply]

The entropy contribution from

x_{i}

, or the mean surprisal of

x_{i}

? Bo Jacoby (talk) 06:02, 2 May 2010 (UTC).[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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

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)[reply]

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}:\mathbb {C} ^{n}\to \mathbb {C}$ are quadratic forms. If n $\geq 2^{d}$ , show that there is some non-zero $x\in \mathbb {C} ^{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 $\forall 1\leq i\leq n,i\neq j,q_{i}(x_{j})=0$ for $1\leq j\leq 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)[reply]

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 $\scriptstyle \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

\scriptstyle \lfloor n/2\rfloor

for the last quadratic form. Note that

\scriptstyle \lfloor n/2\rfloor \geq 2^{d}

because n≥2^d+1. --pm a 14:45, 3 May 2010 (UTC)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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