Determining the feasibility conditions for vector space interference alignment in the K-user MIMO interference channel with constant channel coefficients has attracted much recent attention yet remains unsolved. The main result of this paper is restricted to the symmetric square case where all transmitters and receivers have N antennas, and each user desires d transmit dimensions. We prove that alignment is possible if and only if the number of antennas satisfies N>= d(K+1) 2. We also show a necessary condition for feasibility of alignment with arbitrary system parameters. An algebraic geometry approach is central to the results.
The degrees-of-freedom of a K-user Gaussian interference channel (GIC) has been defined to be the multiple of (1 2)log 2 P at which the maximum sum of achievable rates grows with increasing power P. In this paper, we establish that the degrees-of-freedom of three or more user, real, scalar GICs, viewed as a function of the channel coefficients, is discontinuous at points where all of the coefficients are nonzero rational numbers. More specifically, for all K > 2, we find a class of K-user GICs that is dense in the GIC parameter space for which K 2 degrees-of-freedom are exactly achievable, and we show that the degrees-of-freedom for any GIC with nonzero rational coefficients is strictly smaller than K 2. These results are proved using new connections with number theory and additive combinatorics. In this paper, we develop the machinery of real interference alignment. This machinery is extremely powerful in achieving the sum degrees of freedom (DoF) of single antenna systems. The scheme of real interference alignment is based on designing single-layer and multilayer constellations used for modulating information messages at the transmitters. We show that constellations can be aligned in a similar fashion as that of vectors in multiple antenna systems and space can be broken up into fractional dimensions. The performance analysis of the signaling scheme makes use of a recent result in the field of Diophantine approximation, which states that the convergence part of the Khintchine-Groshev theorem holds for points on nondegenerate manifolds. Using real interference alignment, we obtain the sum DoF of two model channels, namely the Gaussian interference channel (IC) and the X channel. It is proved that the sum DoF of the K-user IC is (K 2) for almost all channel parameters. We also prove that the sum DoF of the X-channel with K transmitters and M receivers is (K M K + M - 1) for almost all channel parameters. An interference alignment example is constructed for the deterministic channel model of the K-user interference channel. The deterministic channel example is then translated into the Gaussian setting, creating the first known example of a fully connected Gaussian K-user interference network with single antenna nodes, real, nonzero and constant channel coefficients, and no propagation delays where the degrees of freedom outerbound is achieved. An analogy is drawn between the propagation delay based interference alignment examples and the deterministic channel model which also allows similar constructions for the two-user X channel as well. Recently, Etkin, Tse, and Wang found the capacity region of the two-user Gaussian interference channel to within 1 bit s Hz. A natural goal is to apply this approach to the Gaussian interference channel with an arbitrary number of users. We make progress towards this goal by finding the capacity region of the many-to-one and one-to-many Gaussian interference channels to within a constant number of bits. The result makes use of a deterministic model to provide insight into the Gaussian channel. The deterministic model makes explicit the dimension of signal level. A central theme emerges: the use of lattice codes for alignment of interfering signals on the signal level.