Search

We study percolation on nonamenable groups at the uniqueness threshold $p_u$, the critical value that separates the phase in which there are infinitely many infinite clusters from the phase in which there is a unique infinite cluster. The number of infinite clusters at $p_u$ itself is a subtle question, depending on the choice of group, with only a relatively small number of examples understood. In this paper, we do the following: 1. Prove non-uniqueness at $p_u$ in a new class of examples, namely those groups that contain an amenable, $wq$-normal subgroup of exponential growth. Concrete new examples to which this result applies include lamplighters over nonamenable base groups. 2. Prove a co-heredity property of a certain strong form of non-uniqueness at $p_u$, stating that this property is inherited from a $wq$-normal subgroup to the entire group. Remarkably, this co-heredity property is the same as that proven for the vanishing of the first $\ell^2$ Betti number by Peterson and Thom (Invent. Math. 2011), supporting the conjecture that the two properties are equivalent. Our proof is based on the method of subgroup relativization, and relies in particular on relativized versions of uniqueness monotonicity, the equivalence of non-uniqueness and connectivity decay, the sharpness of the phase transition, and the Burton-Keane theorem. As a further application of the relative Burton-Keane theorem, we resolve a question of Lyons and Schramm (Ann. Probab. 1999) concerning intersections of random walks with percolation clusters., Comment: 30 pages

We show that in the single-parameter mechanism design environment, the only non-wasteful, symmetric, incentive compatible and sybil-proof mechanism is a second price auction with symmetric tie-breaking. Thus, if there is private information, lotteries or other mechanisms that do not always allocate to a highest-value bidder are not sybil-proof or not incentive compatible.

Using first principles calculations, this work investigates the suitability of diamond/c-BN heterojunctions for high frequency, high power device applications. The key quantities of band offsets and interface charge polarization are examined for different crystallographic orientations [(110), (111), or (100)], bond terminations (C-B or C-N), and substrates (diamond or c-BN). The results indicate that both the (111) and (100) structures with polar interfaces are likely to be a type-I alignment with the diamond conduction and valence band extrema nested within the c-BN bandgap, whereas the non-polar (110) counterpart may form type II as the valence band of c-BN is shifted down substantially lower. The (111) and (100) structures also show net charge polarization in a narrow region at the interface. The electron-deficient and electron-rich nature of the C-B and C-N bonding are found to induce charge redistribution leading to an essentially 2D sheet of negative and positive polarization. With the predicted band alignments suitable for carrier confinement as well as the possibility of the modulation and polarization doping, the diamond/c-BN heterostructures are a promising candidate for high-performance electronic devices with a highly conductive 2D channel. Both p-type and n-type devices appear possible with a judicious choice of the heterojunction configuration., Comment: 18 pages, 5 figures

We introduce asymptotic R\'enyi entropies as a parameterized family of invariants for random walks on groups. These invariants interpolate between various well-studied properties of the random walk, including the growth rate of the group, the Shannon entropy, and the spectral radius. They furthermore offer large deviation counterparts of the Shannon-McMillan-Breiman Theorem. We prove some basic properties of asymptotic R\'enyi entropies that apply to all groups, and discuss their analyticity and positivity for the free group and lamplighter groups., Comment: 25 pages, 1 figure

We study random walks on the integers driven by a sample of time-dependent nearest-neighbor conductances that are bounded but are permitted to vanish over time intervals of positive Lebesgue-length. Assuming only ergodicity of the conductance law under space-time shifts and a moment assumption on the time to accumulate a unit conductance over a given edge, we prove that the walk scales, under a diffusive scaling of space and time, to a non-degenerate Brownian motion for a.e. realization of the environment. The conclusion particularly applies to random walks on one-dimensional dynamical percolation subject to fairly general stationary edge-flip dynamics., Comment: 18 pages

This paper studies relations among axioms on individuals' intertemporal choices under risk. The focus is on Risk Averse over Time Lotteries (RATL), meaning that a fixed prize is preferred to a lottery with the same monetary prize but a random delivery time. Though surveys and lab experiments documented RATL choices, Expected Discounted Utility cannot accommodate any RATL. This paper's contribution is two-fold. First, under a very weak form of Independence, we generalize the incompatibility of RATL with two axioms about intertemporal choices: Stochastic Impatience (SI) and No Future Bias. Next, we prove a representation theorem that gives a class of models satisfying RATL and SI everywhere. This illustrates that there is no fundamental conflict between RATL and SI, and leaves open possibility that RATL behavior is caused by Future Bias.

The main theorem of this paper establishes a uniform syndeticity result concerning the multiple recurrence of measure-preserving actions on probability spaces. More precisely, for any integers $d,l\geq 1$ and any $\varepsilon > 0$, we prove the existence of $\delta>0$ and $K\geq 1$ (dependent only on $d$, $l$, and $\varepsilon$) such that the following holds: Consider a solvable group $\Gamma$ of derived length $l$, a probability space $(X, \mu)$, and $d$ pairwise commuting measure-preserving $\Gamma$-actions $T_1, \ldots, T_d$ on $(X, \mu)$. Let $E$ be a measurable set in $X$ with $\mu(E) \geq \varepsilon$. Then, $K$ many (left) translates of \begin{equation*} \left\{\gamma\in\Gamma\colon \mu(T_1^{\gamma^{-1}}(E)\cap T_2^{\gamma^{-1}} \circ T^{\gamma^{-1}}_1(E)\cap \cdots \cap T^{\gamma^{-1}}_d\circ T^{\gamma^{-1}}_{d-1}\circ \ldots \circ T^{\gamma^{-1}}_1(E))\geq \delta \right\} \end{equation*} cover $\Gamma$. This result extends and refines uniformity results by Furstenberg and Katznelson. As a combinatorial application, we obtain the following uniformity result. For any integers $d,l\geq 1$ and any $\varepsilon > 0$, there are $\delta>0$ and $K\geq 1$ (dependent only on $d$, $l$, and $\varepsilon$) such that for all finite solvable groups $G$ of derived length $l$ and any subset $E\subset G^d$ with $m^{\otimes d}(E)\geq \varepsilon$ (where $m$ is the uniform measure on $G$), we have that $K$-many (left) translates of \begin{multline*} \{g\in G\colon m^{\otimes d}(\{(a_1,\ldots,a_n)\in G^d\colon (a_1,\ldots,a_n),(ga_1,a_2,\ldots,a_n),\ldots,(ga_1,ga_2,\ldots, ga_n)\in E\})\geq \delta \} \end{multline*} cover $G$. The proof of our main result is a consequence of an ultralimit version of Austin's amenable ergodic Szem\'eredi theorem., Comment: [v5]: Improved main results and organization of the paper in response to referee feedback; final version accepted by ETDS

In this paper, we consider the problem of variable-length coding over the class of memoryless binary asymmetric channels (BACs) with noiseless feedback, including the binary symmetric channel (BSC) as a special case. In 2012, Naghshvar et al. introduced an encoding scheme, which we refer to as the small-enough-difference (SED) encoder, which asymptotically achieves both capacity and Burnashev's optimal error exponent for symmetric binary-input channels. Building on the work of Naghshvar et al., this paper extends the SED encoding scheme to the class of BACs and develops a non-asymptotic upper bound on the average blocklength that is shown to achieve both capacity and the optimal error exponent. For the specific case of the BSC, we develop an additional non-asymptotic bound using a two-phase analysis that leverages both a submartingale synthesis and a Markov chain time of first passage analysis. For the BSC with capacity $1/2$, both new achievability bounds exceed the achievability bound of Polyanskiy et al. for a system limited to stop-feedback codes., Comment: 18 pages; submitted to IEEE Transactions on Information Theory

We consider the concatenation of a convolutional code (CC) with an optimized cyclic redundancy check (CRC) code as a promising paradigm for good short blocklength codes. The resulting CRC-aided convolutional code naturally permits the use of serial list Viterbi decoding (SLVD) to achieve maximum-likelihood decoding. The convolutional encoder of interest is of rate-$1/\omega$ and the convolutional code is either zero-terminated (ZT) or tail-biting (TB). The resulting CRC-aided convolutional code is called a CRC-ZTCC or a CRC-TBCC. To design a good CRC-aided convolutional code, we propose the distance-spectrum optimal (DSO) CRC polynomial. A DSO CRC search algorithm for the TBCC is provided. Our analysis reveals that the complexity of SLVD is governed by the expected list rank which converges to $1$ at high SNR. This allows a good performance to be achieved with a small increase in complexity. In this paper, we focus on transmitting $64$ information bits with a rate-$1/2$ convolutional encoder. For a target error probability $10^{-4}$, simulations show that the best CRC-ZTCC approaches the random-coding union (RCU) bound within $0.4$ dB. Several CRC-TBCCs outperform the RCU bound at moderate SNR values., Comment: First revision submitted to IEEE Transactions on Information Theory

Quotient sets have attracted the attention of mathematicians in the past three decades. The set of quotients of primes is dense in the positive real numbers and the set of all quotients of Gaussian primes is also dense in the complex plane. Sittinger has proved that the set of quotients of primes in an imaginary quadratic ring is dense in the complex plane and the set of quotients of primes in a real quadratic number ring is dense in R. An interesting open question is introduced by Sittinger: Is the set of quotients of Hurwitz primes dense in the quaternions? In this paper, we answer the question and prove that the set of all quotients of Hurwitz primes is dense in the quaternions.