Search

We study which integers are admissible as Fourier coefficients of even integer weight newforms. In the specific case of the tau-function, we show that for all odd primes ℓ < 100 and all integers m ≥ 1 , we have τ (n) ≠ ± ℓ , ± 5 m. For general newforms f with even integer weight 2 k and integer coefficients, we prove for most integers j dividing 2 k − 1 and all ordinary primes p that a f (p 2) is never a j -th power. We prove a similar result for a f (p 4) , conditional on the Frey-Mazur Conjecture. Our primary method involves relating questions about values of newforms to the existence of perfect powers in certain binary recurrence sequences, and makes use of bounds from the theory of linear forms in logarithms. The method extends without difficulty to a large family of Lebesgue-Nagell equations with fixed exponent. To prove results about general newforms, we also make use of the modular method and Ribet's level-lowering theorem. [ABSTRACT FROM AUTHOR]

The main subject of this paper are binary pattern sequences, that is, sequences of the form (− 1) # (n , A) where A is a set of strings of 0s and 1s, and # (n , A) denotes the total number of times patterns from A appear in the binary expansion of n. A sequence is said to be noncorrelated if the corresponding spectral measure is equal to the Lebesgue measure. We show that it is possible to algorithmically verify if a given binary pattern sequence is noncorrelated. As an application, we compute that there are exactly 2272 noncorrelated binary pattern sequences of length ≤4. If we restrict our attention to patterns that do not end with 0, we put forward a sufficient condition for a pattern sequence to be noncorrelated. We conjecture that this condition is also necessary, and verify this conjecture for lengths ≤5. [ABSTRACT FROM AUTHOR]

We study the construction of optimal conflict-avoiding codes (CAC) from a number theoretical point of view. The determination of the size of optimal CAC of prime length p and weight 3 is formulated in terms of the solvability of certain twisted Fermat equations of the form g 2 X ℓ + g Y ℓ + 1 = 0 over the finite field F p for some primitive root g modulo p. We treat the problem of solving the twisted Fermat equations in a more general situation by allowing the base field to be any finite extension field F q of F p. We show that for q greater than a lower bound of the order of magnitude O (ℓ 2) there exists a generator g of F q × such that the equation in question is solvable over F q. Using our results we are able to contribute new results to the construction of optimal CAC of prime lengths and weight 3. [ABSTRACT FROM AUTHOR]

For every positive integer n and every δ ∈ 0 , 1 , let B (n , δ) denote the probabilistic model in which a random set A ⊆ { 1 , ... , n } is constructed by choosing independently every element of { 1 , ... , n } with probability δ. Moreover, let (u k) k ≥ 0 be an integer sequence satisfying u k = a 1 u k − 1 + a 2 u k − 2 , for every integer k ≥ 2 , where u 0 = 0 , u 1 ≠ 0 , and a 1 , a 2 are fixed nonzero integers; and let α and β , with | α | ≥ | β | , be the two roots of the polynomial X 2 − a 1 X − a 2. Also, assume that α / β is not a root of unity. We prove that, as δ n / log ⁡ n → + ∞ , for every A in B (n , δ) we have log ⁡ lcm (u a : a ∈ A) ∼ δ Li 2 (1 − δ) 1 − δ ⋅ 3 log ⁡ | α / (a 1 2 , a 2) | π 2 ⋅ n 2 with probability 1 − o (1) , where lcm denotes the lowest common multiple, Li 2 is the dilogarithm, and the factor involving δ is meant to be equal to 1 when δ = 1. This extends previous results of Akiyama, Tropak, Matiyasevich, Guy, Kiss and Mátyás, who studied the deterministic case δ = 1 , and is motivated by an asymptotic formula for lcm (A) due to Cilleruelo, Rué, Šarka, and Zumalacárregui. [ABSTRACT FROM AUTHOR]

A Cullen number is a number of the form m 2 m + 1 , where m is a positive integer. In 2004, Luca and Stănică proved, among other things, that the largest Fibonacci number in the Cullen sequence is F 4 = 3. Actually, they searched for generalized Cullen numbers among some binary recurrence sequences. In this paper, we will work on higher order recurrence sequences. For a given linear recurrence (G n) n , under weak assumptions, and a given polynomial T (x) ∈ Z [ x ] , we shall prove that if G n = m x m + T (x) , then m ≪ 1 and n ≪ log ⁡ | x | , where the implied constants depend only on (G n) n and T (x). [ABSTRACT FROM AUTHOR]

• Through PRBS phase modulation, a narrow-linewidth linearly polarized pulsed laser output with an average power of 30 W, a peak power of 376 kW(repeat frequency of 10 kHz, pulse width of 7.5 ns). • This peak power is the highest index obtained by the reported pulsed fiber laser. The peak power and average power can be further increased by adding an amplifier stage. When designing a fiber laser, it is difficult to achieve both narrow linewidth and high power due to nonlinear effects, especially stimulated Brillouin scattering (SBS). However, using the pseudo-random binary sequence (PRBS) phase modulation technique, SBS can be effectively suppressed in narrow-linewidth fiber lasers during amplification. In light of this, we carried out the experimental research described in this paper. First, based on a theoretical analysis, a narrow-linewidth linearly polarized pulsed fiber laser system was designed; then, an experimental platform of a multistage master-oscillator power amplifier (MOPA) structure was constructed, including one-stage continuous optical amplification and four-stage pulsed optical amplification. In our experiments, without phase modulation, a linearly polarized narrow-linewidth fiber laser achieved an average power output of 17 W and a peak power of 188 kW (repetition frequency of 10 kHz, pulse width of 8.5 ns). At this level of power, the spectral signal-to-noise ratio was about 40 dB, and the beam transmission factors in the X and Y directions were 1.14 and 1.11, respectively. Using PRBS phase modulation, a linearly polarized narrow-linewidth pulsed laser achieved an average power output of 30 W and a peak power of 376 kW (repetition frequency of 10 kHz, pulse width of 7.5 ns) at a clock rate of 1.25 GHz. The polarization extinction ratio was greater than 15 dB, the spectral signal-to-noise ratio was greater than 40 dB, and the beam transmission factors in the X and Y directions were 1.18 and 1.12, respectively. [ABSTRACT FROM AUTHOR]

Abstract The Linear Complexity Test is a statistical test for verifying the randomness of a binary sequence produced by a random number generator (RNG). It is the most time-consuming test in the widely used randomness testing suite that was published by the National Institute of Standards and Technology (NIST). The slow performance of the original Linear Complexity Test implementation is one of the major hurdles in the RNG testing process. In this work, we present a parallelized implementation of the Linear Complexity Test for GPU computation. We incorporate two levels of parallelism and various design optimization approaches to accelerate the test execution on modern GPU architectures. To further enhance the performance, we also create a hybrid computation approach that uses both CPU and GPU simultaneously. We achieve a speedup of more than 4000 times over the original Linear Complexity Test implementation from NIST (27 times over the previous best implementation of the test). Highlights • Parallel implementation of the Linear Complexity Test for GPU computation. • Achieved a speedup of more than several orders of magnitude. • Decision mechanism for finding the ideal workload amount per thread. • A hybrid computing approach that simultaneously utilizes CPU and GPU. [ABSTRACT FROM AUTHOR]

Abstract We study 2-representations, i.e., actions of 2-groups on 2-vector spaces. Our main focus is character theory for 2-representations. To this end we employ the technique of extended Burnside rings. Our main theorem is that the Ganter–Kapranov 2-character is a particular mark homomorphism of the Burnside ring. As an application we give a new proof of Osorno's formula for the Ganter–Kapranov 2-character of a finite group. [ABSTRACT FROM AUTHOR]

Abstract In this article we associate a combinatorial differential graded algebra to a cubic planar graph G. This algebra is defined combinatorially by counting binary sequences, which we introduce, and several explicit computations are provided. In addition, in the appendix by K. Sackel the F q -rational points of its graded augmentation variety are shown to coincide with (q + 1) -colorings of the dual graph. [ABSTRACT FROM AUTHOR]

Abstract Algorithmic learning theory traditionally studies the learnability of effective infinite binary sequences (reals), while recent work by Vitányi and Chater has adapted this framework to the study of learnability of effective probability distributions from random data. We prove that for certain families of probability measures that are parametrized by reals, learnability of a subclass of probability measures is equivalent to learnability of the class of the corresponding real parameters. This equivalence allows to transfer results from classical algorithmic theory to learning theory of probability measures. We present a number of such applications, providing many new results regarding EX and BC learnability of classes of measures, thus drawing parallels between the two learning theories. [ABSTRACT FROM AUTHOR]

Reading more and more bits from an infinite binary sequence that is random for a Bernoulli measure with parameter p , we can get better and better approximations of p using the strong law of large numbers. In this paper, we study a similar situation from the viewpoint of inductive inference. Assume that p is a computable real, and we have to eventually guess the program that computes p . We show that this cannot be done computably, and extend this result to more general computable distributions. We also provide a weak positive result showing that looking at a sequence X generated according to some computable probability measure, we can guess a sequence of algorithms that, starting from some point, compute a measure that makes X Martin-Löf random. [ABSTRACT FROM AUTHOR]

Session types are a formalism used to model structured communication-based programming. A binary session type describes communication by specifying the type and direction of data exchanged between two parties. When session types and session processes are added to the syntax of standard π -calculus they give rise to additional separate syntactic categories. As a consequence, when new type features are added, there is duplication of effort in the theory: the proofs of properties must be checked both on standard types and on session types. We show that session types are encodable into standard π -types, relying on linear and variant types. Besides being an expressivity result, the encoding (i) removes the above redundancies in the syntax, and (ii) the properties of session types are derived as straightforward corollaries, exploiting the corresponding properties of standard π -types. The robustness of the encoding is tested on a few extensions of session types, including subtyping, polymorphism and higher-order communications. [ABSTRACT FROM AUTHOR]

A finite word is closed if it contains a factor that occurs both as a prefix and as a suffix but does not have internal occurrences, otherwise it is open. We are interested in the oc-sequence of a word, which is the binary sequence whose n -th element is 0 if the prefix of length n of the word is open, or 1 if it is closed. We exhibit results showing that this sequence is deeply related to the combinatorial and periodic structure of a word. In the case of Sturmian words, we show that these are uniquely determined (up to renaming letters) by their oc-sequence. Moreover, we prove that the class of finite Sturmian words is a maximal element with this property in the class of binary factorial languages. We then discuss several aspects of Sturmian words that can be expressed through this sequence. Finally, we provide a linear-time algorithm that computes the oc-sequence of a finite word, and a linear-time algorithm that reconstructs a finite Sturmian word from its oc-sequence. [ABSTRACT FROM AUTHOR]

In each of the three projective planes coordinatized by the Knuth’s binary semifield K n of order 2 n and two of its Knuth derivatives, we exhibit a new infinite family of translation hyperovals. In particular, when n = 5 , we also present complete lists of all translation hyperovals in them. The properties of some designs associated with these hyperovals are also studied. [ABSTRACT FROM AUTHOR]

We compare the power of betting strategies (aka martingales ) whose wagers take values in different sets of reals. A martingale whose wagers take values in a set A is called an A -martingale. A set of reals B anticipates a set A , if for every A -martingale there is a countable set of B -martingales, such that on every binary sequence on which the A -martingale gains an infinite amount at least one of the B -martingales gains an infinite amount, too. We show that for two important classes of pairs of sets A and B , B anticipates A if and only if the closure of B contains rA , for some positive r . One class is when A is bounded and B is bounded away from zero; the other class is when B is well ordered. Our results generalize several recent results in algorithmic randomness and answer a question posed by Chalcraft et al. (2012) . [ABSTRACT FROM AUTHOR]

A sequence S is called r-nonrepetitive if no r sequentially adjacent blocks in S are identical. By the classic results of Thue from the beginning of the 20th century, we know that there exist arbitrarily long binary 3-nonrepetitive sequences and ternary 2-nonrepetitive sequences. This discovery stimulated over the years intensive research leading to various generalizations and many exciting problems and results in combinatorics on words. In this paper, we study two fractional versions of nonrepetitive sequences. In the first one, we demand that all subsequences of a sequence S , with gaps bounded by a fixed integer j ≥ 1 , are r -nonrepetitive. (This variant emerged from studying nonrepetitive colorings of the Euclidean plane.) Let π j (r) denote the least size of an alphabet guaranteeing existence of arbitrarily long such sequences. We prove that ⌈ j r − 1 ⌉ + 1 ≤ π j (r) ≤ 2 ⌈ j r − 1 ⌉ + 1 , for all r ≥ 3 and j ≥ 1. We also consider a more general situation with the gap bound j being a real number, and apply this to nonrepetitive coloring of the plane. The second variant allows for using a "fractional" alphabet, analogously as for the fractional coloring of graphs. More specifically, we look for sequences of b -element subsets B 1 , B 2 , ... of an a -element alphabet, with the ratio a / b as small as possible, such that every member of the Cartesian product B 1 × B 2 × ⋯ is r -nonrepetitive. By using the entropy compression argument, we prove that the corresponding parameter π f (r) = inf ⁡ a b can be arbitrarily close to 1 for sufficiently large r. [ABSTRACT FROM AUTHOR]

Text We study how the asymptotic irrationality exponent of a given generalized continued fraction K n = 1 ∞ a n b n , a n , b n ∈ Z + , behaves as a function of growth properties of partial coefficient sequences ( a n ) and ( b n ) . Video For a video summary of this paper, please visit http://youtu.be/u5B2ItY9v28 . [ABSTRACT FROM AUTHOR]

The correlation measure of order k is an important measure of pseudorandomness for binary sequences. This measure tries to look for dependence between several shifted versions of a sequence. We study the relation between the correlation measure of order k and two other pseudorandom measures: the N th linear complexity and the N th maximum order complexity. We simplify and improve several state-of-the-art lower bounds for these two measures using the Hamming bound as well as weaker bounds derived from it. [ABSTRACT FROM AUTHOR]

[Display omitted] • Binary sequence patterns determine sequence-ensemble-function relationships of IDPs. • NARDINI is a new method to uncover non-random binary patterns within IDRs. • NARDINI is illustrated using three distinct examples of biophysical relevance. Sequence-ensemble relationships of intrinsically disordered proteins (IDPs) are governed by binary patterns such as the linear clustering or mixing of specific residues or residue types with respect to one another. To enable the discovery of potentially important, shared patterns across sequence families, we describe a computational method referred to as NARDINI for N on-random A rrangement of R esidues in D isordered R egions I nferred using N umerical I ntermixing. This work was partially motivated by the observation that parameters that are currently in use for describing different binary patterns are not interoperable across IDPs of different amino acid compositions and lengths. In NARDINI, we generate an ensemble of scrambled sequences to set up a composition-specific null model for the patterning parameters of interest. We then compute a series of pattern-specific z-scores to quantify how each pattern deviates from a null model for the IDP of interest. The z-scores help in identifying putative non-random linear sequence patterns within an IDP. We demonstrate the use of NARDINI derived z-scores by identifying sequence patterns in three well-studied IDP systems. We also demonstrate how NARDINI can be deployed to study archetypal IDPs across homologs and orthologs. Overall, NARDINI is likely to aid in designing novel IDPs with a view toward engineering new sequence-function relationships or uncovering cryptic ones. We further propose that the z-scores introduced here are likely to be useful for theoretical and computational descriptions of sequence-ensemble relationships across IDPs of different compositions and lengths. [ABSTRACT FROM AUTHOR]

Sequences with perfect linear complexity profile were defined more than thirty years ago in the study of measures of randomness for binary sequences. More recently apwenian sequences , first with values ±1, then with values in { 0 , 1 } , were introduced in the study of Hankel determinants of automatic sequences. We explain that these two families of sequences are the same up to indexing, and give consequences and questions that this implies. We hope that this will help gathering two distinct communities of researchers. [ABSTRACT FROM AUTHOR]

Visual cryptography scheme (VCS) shares a binary secret image into multiple shadows, only qualified set of shadows can reveal the secret image by stacking operation. However, VCS suffers the problems of low visual quality of the revealed image and large shadow size. A (t , k , n) XOR-based visual cryptography scheme (XVCS) shares the secret image into n shadows including t essentials and n - t non-essentials. A qualified set of shadows contains any k shadows including t essentials. The revealing process is implemented by XOR operation on the involved shadows. In this paper, we propose a construction method for (t , k , n)-XVCS with essential shadows. The secret image can be revealed perfectly, and the shadow size is small compared with VCS. Theoretical analysis and experimental results show the security and effectiveness of the proposed scheme. [ABSTRACT FROM AUTHOR]

Existing parallel algorithms for wavelet tree construction have a work complexity of O (n log ⁡ σ). This paper presents parallel algorithms for the problem with improved work complexity. Our first algorithm is based on parallel integer sorting and has either O (n log ⁡ log ⁡ n ⌈ log ⁡ σ / log ⁡ n log ⁡ log ⁡ n ⌉) work and polylogarithmic depth, or O (n ⌈ log ⁡ σ / log ⁡ n ⌉) work and sub-linear depth. We also describe another algorithm that has O (n ⌈ log ⁡ σ / log ⁡ n ⌉) work and O (σ + log ⁡ n) depth. We then show how to use similar ideas to construct variants of wavelet trees (arbitrary-shaped binary trees and multiary trees) as well as wavelet matrices in parallel with lower work complexity than prior algorithms. Finally, we show that the rank and select structures on binary sequences and multiary sequences, which are stored on wavelet tree nodes, can be constructed in parallel with improved work bounds, matching those of the best existing sequential algorithms for constructing rank and select structures. [ABSTRACT FROM AUTHOR]

We give a simple recursion labeled by binary sequences which computes rational q , t -Catalan power series, both in relatively prime and non relatively prime cases. It is inspired by, but not identical to recursions due to B. Elias, M. Hogancamp, and A. Mellit, obtained in their study of link homology. We also compare our recursion with the Hogancamp-Mellit's recursion and verify a connection between the Khovanov-Rozansky homology of N , M -torus links and the rational q , t -Catalan power series for general positive N , M. [ABSTRACT FROM AUTHOR]

In this paper, we generalize the notion of functional graph. Specifically, given an equation E (X , Y) = 0 with variables X and Y over a finite field F q of odd characteristic, we define a digraph by choosing the elements in F q as vertices and drawing an edge from x to y if and only if E (x , y) = 0. We call this graph as equational graph. In this paper, we study the equational graph when choosing E (X , Y) = (Y 2 − f (X)) (λ Y 2 − f (X)) with f (X) a polynomial over F q and λ a non-square element in F q. We show that if f is a permutation polynomial over F q , then every connected component of the graph has a Hamiltonian cycle. Moreover, these Hamiltonian cycles can be used to construct balancing binary sequences. By making computations for permutation polynomials f of low degree, it appears that almost all these graphs are strongly connected, and there are many Hamiltonian cycles in such a graph if it is connected. [ABSTRACT FROM AUTHOR]

Systematic comparison of multiple plasmids remains challenging. We aimed to develop a new method for phylogenetic analysis of plasmids, open reading frame (ORF)-based binarized structure network analysis of plasmids (OSNAp). With the OSNAp, the genetic structures of plasmids in a given plasmid group are expressed as binary sequences based on the presence or absence of ORFs regardless of their positions or directions. As a proof-of-concept, ORFs were collected from 101 complete I1 plasmid sequences, and their corresponding binary sequences were generated. A tree was generated using the neighbor-net, an algorithm for constructing phylogenetic networks based on distance between taxa, to visualize the plasmid phylogeny drawn from binary sequences. The results were compared with those of plasmid sequence types (pSTs) defined by plasmid multilocus sequence typing (pMLST). All I1 plasmids were placed on the phylogenetic tree constructed from the binary sequences. Most plasmids belonging to the same pSTs had Dice indices of ≥0.95 and were placed in the same OSNAp split. On the other hand, pST12 plasmids were distributed on separate splits due to differences in ORFs not used in pMLST, suggesting improved differentiation of the plasmids with OSNAp compared with pMLST. OSNAp is a novel holistic approach to assess relatedness of a population of plasmids in a given plasmid group based on nucleotide sequence data. It provides higher discrimination than pMLST, which may prove useful in tracing bacteria that harbor plasmids of shared origins. • OSNAp, a new phylogenetic analysis method of plasmids was developed. • Plasmid structures are expressed as binary sequences based on their gene contents. • Phylogeny of plasmids are then visualized as a neighbor-net network. • OSNAp does not require the presence of common sequences among the plasmids. • Application of OSNAp is illustrated using I1 plasmids. [ABSTRACT FROM AUTHOR]