arbitrary alphabets. If we introduce some randomness into the construction as in [7], it is possible to polarize sources over arbitrary alphabets, still maintaining the O ( N log N ) complexity of the construction. Helpful discussions with E. S ¸as¸o˘glu and S. B. Korada are gratefully acknowledged. This work was supported in part by The Scientific and Technological Research Council of Turkey (T ¨ UB ˙ ITAK) under contract no. 107E216, and in part by the European Commission FP7 Network of Excellence NEWCOM++ (contract no. 216715). and tries to recover ( X $^{N}$,Y $^{N}$) with vanishing probability of error. The well-known Slepian-Wolf theorem states that this is possible provided R$_{x}$ ≥ H ( X | Y ) , R$_{y}$ ≥ H ( Y | X ) , and R$_{x}$ + R$_{y}$ ≥ H ( X,Y ) . It is straightforward to design a polar coding scheme that achieves the corner point ( H ( X | Y ) ,H ( Y )) of the Slepian- Wolf rate region. Fix R$_{y}$ > H ( Y ) and R$_{x}$ > H ( X | Y ) . For N = 2 $^{n}$, n ≥ 1 , consider a pair of high-entropy sets E$_{Y}$ = E$_{Y}$ ( N,R$_{y}$ ) and E$_{X}$$_{|}$$_{Y}$ = E$_{X}$$_{|}$$_{Y}$ ( N,R$_{x}$ ) . Encoding: Given a realization X N = x $^{N}$, encoder 1 calculates u N = x $^{N}$G$_{N}$ and sends u$_{E}$$_{X}$$_{|}$$_{Y}$ to the common decoder. Given a realization Y N = y $^{N}$, encoder 2 calculates v N = y $^{N}$G$_{N}$ and sends v$_{E}$$_{Y}$ . Decoding: The decoder first applies the decoding algorithm of Section III to obtain an estimate ˆ y N of y N from v$_{E}$$_{Y}$ . Next, the decoder applies the same algorithm to obtain an estimate of x N using ˆ y N (as a substitute for the actual realization y $^{N}$) and u$_{E}$$_{X}$$_{|}$$_{Y}$ . We omit the analysis of this scheme since it essentially consists of two single-user source coding schemes of the type treated in Section III. It is clear that polar coding can achieve all points of the Slepian-Wolf region by time-sharing between the corner points ( H ( X ) ,H ( X | Y )) and ( H ( X | Y ) ,H ( Y )) . We should remark that polar coding for Slepian-Wolf prob- lem was first studied in [6], [2], and [3] under the assumption s that X,Y ∼ Ber ( 1 $_{2}$) , and X ⊕ Y ∼ Ber ( p ) . The above approach to Slepian-Wolf coding reduces the problem to single-user source coding problems. A direct appoach would be to have each encoder apply polar transforms locally, with encoder 1 computing U N = X $^{N}$G$_{N}$ and encoder 2 computing V N = Y $^{N}$G$_{N}$ . Preliminary analyses show that such local operations polarize X N 1 and Y N 1 not only individually but also in a joint sense. A detailed study of such schemes is left for future work. Inspection of the third order derivative shows that dF/dp is strictly convex for p ∈ [0 , 1 $_{2}$) and strictly concave for p ∈ ( 1 $_{2}$, 1] . Thus, dF/dp = 0 can have at most one solution in each interval [0 , 1 $_{2}$) and ( 1 $_{2}$, 1] . Since dF/dp = 0 at p = 1 $_{2}$, the number of zeros of dF/dp over [0 , 1] is at most three. Thus, F ( p ) can have at most three zeros over [0 , 1] . Since F ( p ) = 0 for p ∈ { 0 , 1 $_{2}$, 1 } , there can be no other zeros. Thus, for any pair of random variables ( X,Y ) with X binary, if we condition on Y = y , we have First we prove that Z ( X ) 2 ≤ H ( X ) for any X ∼ Ber ( p ) with equality if and only if p ∈ { 0 , 1 $_{2}$, 1 } . Let F ( p ) = H ( Z ) − Z ( X ) 2 = − p log$_{2}$( p ) − (1 − p ) log$_{2}$(1 − p ) − 4 p (1 − p ) , and compute Theorem 4. Let X ∼ P$_{X}$ be a memoryless source over X = { 0 , 1 ,...,q − 1 } for some prime q ≥ 2 . For n ≥ 1 and N = 2 $^{n}$, let X N = ( X$_{1}$,...,X$_{N}$ ) be N independent drawings from the source X . Let U N = X $^{N}$G$_{N}$ where G$_{N}$ is as defined in (3) but the matrix operation is now carried out in GF( q ). Then, the polarization limits in Theorem 1 remain valid provided the entropy terms are calculated with respect to base- q logarithms. Averaging over Y , and by Jensen’s inequality, we obtain (4). Recall that the R´enyi entropy of order α ( α > 0 , α = 1 ) for a RV X is defined as and has the following properties [8]. Now suppose X ∼ Ber ( p ) and note that If q is not prime, the theorem may fail. Consider X over { 0 , 1 , 2 , 3 } with P$_{X}$ (0) = P$_{X}$ (2) = 1 $_{2}$. Then, it is straightforward to check that U N has the same distribution as X N for all N . On closer inspection, we realize that X is actually a binary source under disguise. More precisely, X is already polarized over { 0 , 2 } , which is a subfield of GF (4) , and vectors over this subfield are closed under multiplicati on by G$_{N}$ . The preceding example illustrates the difficulties in mak- ing a general statement regarding source polarization over Z ( X | Y = y ) 2 ≤ H ( X | Y = y ) . H$_{α}$ ( X ) = 1 1 − α log ∑ x P$_{X}$ ( x ) α H 1 $_{2}$( X ) = log [ ∑ x √ P$_{X}$ ( x ) ] 2 = log(1 + Z ( X )) . VI. POLARIZATION OF NON-BINARY MEMORYLESS SOURCES B. Proof of Inequality (5) A. Proof of Inequality (4) VII. APPENDIX ACKNOWLEDGMENT dF dp = 1 ln 2 [ − ln p + ln(1 − p )] − 4 + 8 p, d $^{2}$F dp 2 = 1 ln 2 [ − 1 p − 1 1 − p ] + 8 , d $^{3}$F dp 3 = 1 ln 2 [ 1 p 2 − 1 (1 − p ) 2 ] . • H$_{α}$ ( X ) is strictly decreasing in α unless P$_{X}$ is uniform on its support Supp ( X ) = { x : P$_{X}$ ( x ) > 0 } . • H ( X ) = lim$_{α}$$_{→}$$_{1}$ H$_{α}$ ( X ) .