Search

We consider the problem of communicating over a channel that randomly “tears” the message block into small pieces of different sizes and shuffles them. For the binary torn-paper channel with block length $n$ and pieces of length ${\mathrm{ Geometric}}(p_{n})$ , we characterize the capacity as $C = e^{-\alpha }$ , where $\alpha = \lim _{n\to \infty } p_{n} \log n$ . Our results show that the case of ${\mathrm{ Geometric}}(p_{n})$ -length fragments and the case of deterministic length- $(1/p_{n})$ fragments are qualitatively different and, surprisingly, the capacity of the former is larger. Intuitively, this is due to the fact that, in the random fragments case, large fragments are sometimes observed, which boosts the capacity.

We show that a smooth embedded paper Moebius band must have aspect ratio at least $$\begin{aligned}\lambda _1= \frac{2 \sqrt{4-2 \sqrt{3}}+4}{\root 4 \of {3} \sqrt{2}+2 \sqrt{2 \sqrt{3}-3}} =1.69497\ldots \end{aligned}$$ This bound comes more than 3/4 of the way from the old known bound of $$\pi /2=1.5708\ldots $$ to the conjectured bound of $$\sqrt{3} = 1.732\ldots $$

Very recently, I. Altun, M. Aslantas and H. Sahin [1] introduced the notion of $$p$$ -proximal contractions and surveyed the existence of best proximity points for such class of non-self mappings in metric spaces. In this note we show that this existence result is a straightforward consequence of the same conclusion in fixed point theory.

Sendov’s conjecture states that if all the zeroes of a complex polynomial P(z) of degree at least two lie in the unit disk, then within a unit distance of each zero lies a critical point of P(z). In a paper that appeared in 2014, Degot proved that, for each a ∈ (0, 1), there exists an integer N such that for any polynomial P(z) with degree greater than N, if P(a) = 0 and all zeroes lie inside the unit disk, the disk |z − a| ≤ 1 contains a critical point of P(z). Based on this result, we derive an explicit formula N(a) for each a ∈ (0, 1) and, consequently obtain a uniform bound N for all a ∈ [α, β] where 0 < α < β < 1. This (partially) addresses the questions posed in Degot’s paper.

Wu et al. (Nature 566:378–382, 2019) introduced a new indicator measuring disruption ($${DI}_{1}$$DI1). Bornmann et al. (Do disruption index indicators measure what they propose to measure? The comparison of several indicator variants with assessments by peers, 2019. https://arxiv.org/abs/1911.08775) compared variants of the disruption index and pointed to $${DI}_{5}$$DI5 as an interesting variant. The calculation of a field-specific version of $${DI}_{5}$$DI5 (focusing on disruptiveness within the same field) for Scientometrics papers in the current study reveals that the variant is possibly able to identify landmark papers in scientometrics. This result is in contrast to the Scientometrics analysis previously published by Bornmann and Tekles (Scientometrics 120(1):331–336, 2019) based on the original disruption index ($${DI}_{1}$$DI1).

Cooperation among kin is common in animal societies. Kin groups may form by individuals directly discriminating relatives based on kin recognition cues, or form passively through natal philopatry and limited dispersal. We describe the genetic landscape for a primitively eusocial wasp, Polistes dominula, and ask whether individuals choose cooperative partners that are nearby and/or that are genetic relatives. Firstly, we genotyped an entire sub-population of 1361 wasps and found genetic structuring on an extremely fine scale: the probability of finding genetic relatives decreases exponentially within just a few meters of an individual’s nest. At the same time, however, we found a lack of genetic structuring between natural nest aggregations within the population. Secondly, in a separate dataset where ~2000 wasps were genotyped, we show that wasps forced experimentally to make a new nest choice tended to choose new nests near to their original nests, and that these nests tended to contain some full sisters. However, a significant fraction of wasps chose nests that did not contain sisters, despite sisters being present in nearby nests. Although we cannot rule out a role for direct kin recognition or natal nest-mate recognition, our data suggest that kin groups may form via a philopatric rule-of-thumb, whereby wasps simply select groups and nesting sites that are nearby. The result is that most subordinate helpers obtain indirect fitness benefits by breeding cooperatively.

We introduce a graph Ramsey game called Ramsey, Paper, Scissors. This game has two players, Proposer and Decider. Starting from an empty graph on $n$ vertices, on each turn Proposer proposes a potential edge and Decider simultaneously decides (without knowing Proposer's choice) whether to add it to the graph. Proposer cannot propose an edge which would create a triangle in the graph. The game ends when Proposer has no legal moves remaining, and Proposer wins if the final graph has independence number at least $s$. We prove a threshold phenomenon exists for this game by exhibiting randomized strategies for both players that are optimal up to constants. Namely, there exist constants $0B\sqrt{n}\log{n}$. This is a factor of $\Theta(\sqrt{\log{n}})$ larger than the lower bound coming from the off-diagonal Ramsey number $r(3,s)$.

We correct some mistakes in the paper “A mass formula for negacyclic codes of length 2k and some good negacyclic codes over $\mathbb {Z}_{4}+u\mathbb {Z}_{4}$ ” (Bandi et al. Cryptogr. Commun. 9, 241–272, 2017).

If $$z\in {\mathbb {C}}$$ and $$1\le n$$ is a natural number then $$\begin{aligned} \sum _{d_1 d_2 =n} (1-z^{p_1})\cdots (1-z^{p_m}) z^{q_1 e_{1}+\cdots +q_i e_{i} }=1, \end{aligned}$$ where $$d_1=p_1^{r_1}\dots p_m^{r_m }$$ , $$d_2=q_1^{e_1}\dots q_i^{e_i }$$ are the prime decompositions of $$d_1, d_2$$ . This is one of the identities involving arithmetic functions that we prove using ideas from the paper of Dressler and van de Lune [3].

The main result of this paper states that if $${\mathcal {F}}$$ is a subgroup-closed saturated formation of full characteristic, then the $${\mathcal {F}}$$ -residual of a K- $${\mathcal {F}}$$ -subnormal subgroup S of a finite group G is a large subgroup of G provided that the $${\mathcal {F}}$$ -hypercentre of every subgroup X of G containing S is contained in the $${\mathcal {F}}$$ -residual of X. This extends a recent result of Aivazidis, Safonova and Skiba.

This paper studies the second-order coding rates for memoryless channels with a state sequence known non-causally at the encoder. In the case of finite alphabets, an achievability result is obtained using constant-composition random coding, and by using a small fraction of the block to transmit the empirical distribution of the state sequence. For error probabilities less than 0.5, it is shown that the second-order rate improves on an existing one based on independent and identically distributed random coding. In the Gaussian case (dirty paper coding) with an almost-sure power constraint, an achievability result is obtained using random coding over the surface of a sphere, and using a small fraction of the block to transmit a quantized description of the state power. It is shown that the second-order asymptotics are identical to the single-user Gaussian channel of the same input power without a state.

We study the problem of transmitting a message over a channel that randomly breaks the message block into small fragments, deletes a subset of them, and shuffles the remaining fragments. We characterize the capacity of the binary torn-paper channel under arbitrary fragment length distribution and fragment deletion probabilities. We show that, for a message with block length $n$ , discarding fragments shorter than $\log(n)$ does not affect the achievable rates, and that the capacity is given by a simple closed-form expression that can be understood as “coverage minus reordering-cost”.

Very recently Bordelles, Dai, Heyman, Pan and Shparlinski studied asymptotic behaviour of the quantity $$\begin{aligned} S_f(x) := \sum _{n\leqslant x} f\left( \left[ \frac{x}{n}\right] \right) , \end{aligned}$$and established some asymptotic formulas for $$S_f(x)$$ under three different types of assumptions on f. In this short note we improve some of their results.

Let l be a Banach sequence space with a monotone norm in which the canonical system (e_{n}) is an unconditional basis. We show that if there exists a continuous linear unbounded operator between l-K\"{o}the spaces, then there exists a continuous unbounded quasi-diagonal operator between them. Using this result, we study in terms of corresponding K\"{o}the matrices when every continuous linear operator between l-K\"{o}the spaces is bounded. As an application, we observe that the existence of an unbounded operator between l-K\"{o}the spaces, under a splitting condition, causes the existence of a common basic subspace.

We analytically prove that the outage capacity of the multiple input multiple output (MIMO) which is affected by interference, that is non-causally available as well as the channel state information (CSI) for all users at the transmitter, has the free interference outage capacity. Specifically, Orthogonal space-time block coding (O-STBC) with two transmit antennas and arbitrary number of receive antennas is used for transmission and reception. We modify the random variable U which was proposed by Costa (1983) to account for the availability of the CSI at both the transmitter and receiver. Further, we use lattice dirty paper coding (DPC) to show that an interference free channel capacity can be achieved in the MIMO-OSTBC system. First, we derive the equivalent noise seen by the receiver using an equivalent lattice based dirty paper code. Then the optimal value of the power inflation factor is derived. Next, the channel capacity of the equivalent modulo lattice channel is computed. Finally, performance results in the case of various number of receive antennas are presented and showed that significant reduction in frame error probabilities can be obtained over a system that uses no interference cancellation.

Recently, metapopulation models for rock-paper-scissors games have been presented. Each subpopulation is represented by a node on a graph. An individual is either rock (R), scissors (S) or paper (P); it randomly migrates among subpopulations. In the present paper, we assume victory rates differ in different subpopulations. To investigate the dynamic state of each subpopulation (node), we numerically obtain the solutions of reaction-diffusion equations on the graphs with two and three nodes. In the case of homogeneous victory rates, we find each subpopulation has a periodic solution with neutral stability. However, when victory rates between subpopulations are heterogeneous, the solution approaches stable focuses. The heterogeneity of victory rates promotes the coexistence of species.

Thamarai Selvi and Vaidya Nathan [2] discussed maximum distance on graphs. We made an extension of that paper [2]. We discussed about complete graph Kn, star graph Sn, the complete bipartite graph Km,n. In this paper, we studied about the cycle graph Cn (n being any interger ≥ 3) and the multi star graph Bm,n, where m, n are integers, both greater than or equal to 2.

The problem of chasing convex functions is easy to state: faced with a sequence of convex functions f t over d-dimensional Euclidean spaces, the goal of the algorithm is to output a point x t at each time, so that the sum of the function costs f t (x t ), plus the movement costs ||x t − x t − 1 || is minimized. This problem generalizes questions in online algorithms such as caching and the k-server problem. In 1994, Friedman and Linial posed the question of getting an algorithm with a competitive ratio that depends only on the dimension d. In this talk we give an O (d)-competitive algorithm, based on the notion of the Steiner point of a convex body.

Let \(\mathbb {G}\) be a group of prime order p with a generator g. We first show that if \(p-1=d_1 \ldots d_t\) and \(g,g^x\), \( g^{x^{(p-1)/d_1}}, \ldots , \ g^{x^{(p-1)/(d_1 \ldots d_{t-1})}}\) are given, then x can be computed in time \( O(\sqrt{d_1}+ \ldots + \sqrt{d_t} ) \) exponentiations. Further suppose that \(p-1=d_1^{e_1} \ldots d_t^{e_t}\), where \(d_1, \ldots , d_t\) are relatively prime. We then show that x can be computed in time \( O(e_1\sqrt{d_1}+\ldots + e_t\sqrt{d_t}) \) exponentiations if g and \( g^{x^{(p-1)/d_i}}, \ldots , g^{x^{(p-1)/d_i^{e_i-1}}} \) are given for \(i=1, \ldots , t\).

This paper aims at presenting pairs of rectangles representing the same sphenic number where, in each pair, the sum of the areas is 2 times sphenic number -1

We consider the problem of communicating over a channel that randomly "tears" the message block into small pieces of different sizes and shuffles them. For the binary torn-paper channel with block length $n$ and pieces of length ${\rm Geometric}(p_n)$, we characterize the capacity as $C = e^{-\alpha}$, where $\alpha = \lim_{n\to\infty} p_n \log n$. Our results show that the case of ${\rm Geometric}(p_n)$-length fragments and the case of deterministic length-$(1/p_n)$ fragments are qualitatively different and, surprisingly, the capacity of the former is larger. Intuitively, this is due to the fact that, in the random fragments case, large fragments are sometimes observed, which boosts the capacity.

We give common generalizations of the Menon-type identities by Sivaramakrishnan (1969) and Li, Kim, Qiao (2019). Our general identities involve arithmetic functions of several variables, and also contain, as special cases, identities for gcd-sum type functions. We point out a new Menon-type identity concerning the lcm function. We present a simple character free approach for the proof., Comment: 14 pages

O. Einstein (2008) proved Bollob\'as-type theorems on intersecting families of ordered sets of finite sets and subspaces. Unfortunately, we report that the proof of a theorem on ordered sets of subspaces had a mistake. We prove two weaker variants., Comment: 6 pages. Improved bound for Theorem 4

In this short paper, we look into a conclusion drawn by Alzalg (J Optim Theory Appl 169:32---49, 2016). We think the conclusion drawn in the paper is incorrect by pointing out three things. First, we provide a counterexample that the proposed inner product does not satisfy bilinearity. Secondly, we offer an argument why a pth-order cone cannot be self-dual under any reasonable inner product structure on $$\mathbb {R}^n$$Rn. Thirdly, even under the assumption that all elements operator commute, the inner product becomes an official inner product and the arbitrary-order cone can be shown as a symmetric cone, we think this condition is still unreasonable and very stringent so that the result can only be applied to very few cases.

In this paper, we revisit the problem of factoring RSA moduli with implicit hint, where primes of two RSA moduli share some number of middle bits. Suppose that for two n-bit RSA moduli $$N_1=p_1q_1$$N1=p1q1 and $$N_2=p_2q_2$$N2=p2q2, $$q_1$$q1 and $$q_2$$q2 are $$\alpha n$$αn-bit primes, $$p_1$$p1 and $$p_2$$p2 share tn bits at positions from $$t_1n$$t1n to $$t_2n=t_1+tn$$t2n=t1+tn. Faug$$\grave{e}$$e`re et al. PKC 2010 showed that when $$t\ge 4\alpha $$ti¾?4α, one can factor $$N_1$$N1 and $$N_2$$N2 in polynomial time. In this paper, we improve this bound to $$t>4\alpha -3\alpha ^2$$t>4α-3α2 by presenting a new method of solving a homogeneous linear equation modulo unknown divisors. Our method is verified by experiments.

We present a silent self-stabilizing distributed algorithm computing a maximal p-star decomposition of the underlying communication network. Under the unfair distributed scheduler, the most general scheduler model, the algorithm converges in at most \(12\varDelta m + \mathcal {O}(m+n)\) moves, where m is the number of edges, n is the number of nodes, and \(\varDelta \) is the maximum node degree. Regarding the move complexity, our algorithm outperforms the previously known best algorithm by a factor of \(\varDelta \). While the round complexity for the previous algorithm was unknown, we show a \(5\left\lfloor \frac{n}{p+1} \right\rfloor +5\) bound for our algorithm.

We study leader election in unidirectional rings of homonym processes that have no a priori knowledge on the number of processes. We show that message-terminating leader election is impossible for any class of rings \(\mathcal K_k\) with bounded multiplicity \(k \ge 2\). However, we show that process-terminating leader election is possible in the sub-class \(\mathcal U^* \cap \mathcal K_k\), where \(\mathcal U^*\) is the class of rings which contain a process with a unique label.

The "writing on dirty paper"-channel model offers an information-theoretic framework for precoding techniques for canceling arbitrary interference known at the transmitter. It indicates that lossless precoding is theoretically possible at any signal-to-noise ratio (SNR), and thus dirty-paper coding may serve as a basic building block in both single-user and multiuser communication systems. We design an end-to-end coding realization of a system materializing a significant portion of the promised gains. We employ multidimensional quantization based on trellis shaping at the transmitter. Coset decoding is implemented at the receiver using "virtual bits." Combined with iterative decoding of capacity-approaching codes we achieve an improvement of 2dB over the best scalar quantization scheme. Code design is done using the EXIT chart technique.

This paper again specifies the major points of the article “Do Prime Numbers Obey a Three-Dimensional Double Helix?” [1] which was received on February 16, 2006 by Hadronic Journal. New information has been added and elucidated upon, such as why the numbers 2 and 3 are not considered true prime numbers, and why s in the following formulas for 6s - 1 and for 6s + 1 is really a composite number equal to the sum of two other numbers, suggesting that s is always to be considered as an integer. Other new information is added as well, such as how an engineer in a matter of seconds decomposed a large prime product into its constituent primes using basic software and won a contract for his firm.

In their celebrated paper (Furst et al., Math. Syst. Theory 17(1), 13---27 (12)), Furst, Saxe, and Sipser used random restrictions to reveal the weakness of Boolean circuits of bounded depth, establishing that constant-depth and polynomial-size circuits cannot compute the parity function. Such local restrictions have played important roles and have found many applications in complexity analysis and algorithm design over the past three decades. In this article, we give a brief overview of two intriguing applications of local restrictions: the first one is for the Isomorphism Conjecture and the second one is for moderately exponential time algorithms for the Boolean formula satisfiability problem.

We model the folding of ordinary paper via piecewise isometries R 2 → R 3 . The collection of crease lines and vertices in the unfolded paper is called the crease pattern. Our results generalize the previously known necessity conditions from the more restrictive case of folding paper flat (into R 2 ); if the crease pattern is foldable, then the product (in a non-intuitive order) of the associated rotational matrices is the identity matrix. This condition holds locally in a multiple vertex crease pattern and can be adapted to a global condition. Sufficiency conditions are significantly harder, and are not known except in the two-dimensional single-vertex case.

We analyze the multiauthorship matrix M, defined as the matrix where a cell M (j, @k) denotes the number of times authors with j publications are ranked as the @k^t^h author of an article. We prove that if the distribution of the number of authors per paper follows a power law, then the author rank distribution is approximately equal to this power law (more precisely, equal in Landau's big O sense). We further determine the author rank distribution in the case where authors can be characterized through a seed number; this is the probability of preceding a fixed author in the byline of an article. Such a seed is determined for alphabetical ranking of authors using the standard western alphabet.

Let a(n) be the Fourier coefficient of a holomorphic cusp form on some discrete subgroup of \(SL_2({\mathbb R})\). This note is to refine a recent result of Hofmann and Kohnen on the non-positive (resp. non-negative) product of \(a(n)a(n+r)\) for a fixed positive integer r.

We consider the problem of constructing a matching in an n-nodes graph in a distributed and self-stabilizing manner. We prove that there exists a lower bound in space of \(\varOmega (n\log n)\) bits for universal maximal matching algorithms, and a lower bound in time of \(\varOmega (e)\) moves for universal and cautious 1-maximal matching algorithms. A side contribution of our result is the optimality in both time and space of the self-stabilizing 1-maximal matching algorithm of Inoue et al. [8].