Blowing up solutions for Neumann problem with critical nonlinearity on the boundary

Let G be a transitive permutation group on a finite set of size at least 2. By a well known theorem of Fein, Kantor and Schacher, G contains a derangement of prime power order. In this paper, we study the finite primitive permutation groups with the extremal property that the order of every derangement is an r-power, for some fixed prime r. First we show that these groups are either almost simple or affine, and we determine all the almost simple groups with this property. We also prove that an affine group G has this property if and only if every two-point stabilizer is an r-group. Here the structure of G has been extensively studied in work of Guralnick and Wiegand on the multiplicative structure of Galois field extensions, and in later work of Fleischmann, Lempken and Tiep on \({r'}\)-semiregular pairs.     

Binomial and factorial congruences for Fq[t]

We present several elementary theorems, observations and questions related to the theme of congruences satisfied by binomial coefficients and factorials modulo primes (or prime powers) in the setting of polynomial ring over a finite field. When we look at the factorial of n or the binomial coefficient ‘n choose m’ in this setting, though the values are in a function field, n and m can be usual integers, polynomials or mixed. Thus there are several interesting analogs of the well-known theorems of Lucas, Wilson etc. with quite different proofs and new phenomena.     

Periodic multisequences with large error linear complexity

Generalizing the theory of k-error linear complexity for single sequences over a finite field, Meidl et al. (J. Complexity 23(2), 169–192 (2007)) introduced three possibilities of defining error linear complexity measures for multisequences. A good keystream sequence must possess a large linear complexity and a large k-error linear complexity simultaneously for suitable values of k. In this direction several results on the existence, and lower bounds on the number, of single sequences with large k-error linear complexity were proved in Meidl and Niederreiter (Appl. Algebra Eng. Commun. Comput. 14(4), 273–286 (2003)), Niederreiter (IEEE Trans. Inform. Theory 49(2), 501–505 (2003)) and Niederreiter and Shparlinski (In: Paterson (ed.) 9th IMA International Conference on Cryptography and Coding (2003)). In this paper we discuss analogous results for the case of multisequences. We also present improved bounds on the error linear complexity and on the number of sequences satisfying such bounds for the case of single sequences.     

New generalized cyclotomic binary sequences of period $$p^2$$

New generalized cyclotomic binary sequences of period \(p^2\) are proposed in this paper, where p is an odd prime. The sequences are almost balanced and their linear complexity is determined. The result shows that the proposed sequences have very large linear complexity if p is a non-Wieferich prime.     

On the Unitary Similarity of Matrix Families

The classical Specht criterion for the unitary similarity between two complex n × n matrices is extended to the unitary similarity between two normal matrix sets of cardinality m. This property means that the algebra generated by a set is closed with respect to the conjugate transpose operation. Similar to the well-known result of Pearcy that supplements Specht's theorem, the proposed extension can be made a finite criterion. The complexity of this criterion depends on n as well as the length l of the algebras under analysis. For a pair of matrices, this complexity can be significantly lower than that of the Specht--Pearcy criterion.     

Linear Complexity,k-Error Linear Complexity,and the Discrete Fourier Transform

Complexity measures for sequences of elements of a finite field play an important role in cryptology. We focus first on the linear complexity of periodic sequences. By means of the discrete Fourier transform, we determine the number of periodic sequences S with given prime period length N and linear complexity L_N, 0(S)=c as well as the expected value of the linear complexity of N-periodic sequences. Cryptographically strong sequences should not only have a large linear complexity, but also the change of a few terms should not cause a significant decrease of the linear complexity. This requirement leads to the concept of the k-error linear complexity L_N, k(S) of sequences S with period length N. For some k and c we determine the number of periodic sequences S with given period length N and L_N, k(S)=c. For prime N we establish a lower bound on the expected value of the k-error linear complexity.     

On the structure of 3-nets embedded in a projective plane

We investigate finite 3-nets embedded in a projective plane over a (finite or infinite) field of any characteristic p. Such an embedding is regular when each of the three classes of the 3-net comprises concurrent lines, and irregular otherwise. It is completely irregular when no class of the 3-net consists of concurrent lines. We are interested in embeddings of 3-nets which are irregular but the lines of one class are concurrent. For an irregular embedding of a 3-net of order n?5 we prove that, if all lines from two classes are tangent to the same irreducible conic, then all lines from the third class are concurrent. We also prove the converse provided that the order n of the 3-net is smaller than p. In the complex plane, apart from a sporadic example of order n=5 due to Stipins [7], each known irregularly embedded 3-net has the property that all its lines are tangent to a plane cubic curve. Actually, the procedure of constructing irregular 3-nets with this property works over any field. In positive characteristic, we present some more examples for n?5 and give a complete classification for n=4.     

Epimorphisms in cylindric algebras and definability in finite variable logic

The main result gives a sufficient condition for a class K of finite dimensional cylindric algebras to have the property that not every epimorphism in K is surjective. In particular, not all epimorphisms are surjective in the classes CA _n of n-dimensional cylindric algebras and the class of representable algebras in CA _n for finite n > 1, solving Problem 10 of “Cylindric Set algebras”, by Henkin, et al. for finite n. By a result of Németi, this shows that the Beth-definability property fails for the finite-variable fragments of first order logic as long as the number n of variables available is greater than 1 and we allow models of size ≥ n + 2, but holds if we allow only models of size ≤ n + 1. We also use our results in the present paper to prove that several theorems in the literature concerning injective algebras and definability of polyadic operations in CA _n are best possible. We raise several open problems.     

The Asymptotic Behavior of the Joint Linear Complexity Profile of Multisequences

We prove a conjecture on the asymptotic behavior of the joint linear complexity profile of random multisequences over a finite field. This conjecture was previously shown only in the special cases of single sequences and pairs of sequences. We also establish an asymptotic formula for the expected value of the nth joint linear complexity of random multisequences over a finite field. Some more precise results are shown for triples of sequences.     

Combinatorial constructions for optimal 2-D optical orthogonal codes with AM-OPPTS property

We develop a new one-to-one correspondence between a two-dimensional (m × n, k, ρ) optical orthogonal code (2-D (m × n, k, ρ)-OOC) with AM-OPPTS (at most one-pulse per time slot) property and a certain combinatorial subject, called an n-cyclic holey packing of type m ⁿ . By this link, an upper bound on the size of a 2-D (m × n, k, ρ)-OOC with AM-OPPTS property is derived. Afterwards, we employ combinatorial methods to construct infinitely many 2-D (m × n, k, 1)-OOCs with AM-OPPTS property, whose existence was previously unknown. All these constructions meet the upper bounds with equality and are thus optimal.     

Finiteness of circulant weighing matrices of fixed weight

Let n be a fixed positive integer. Every circulant weighing matrix of weight n arises from what we call an irreducible orthogonal family of weight n. We show that the number of irreducible orthogonal families of weight n is finite and thus obtain a finite algorithm for classifying all circulant weighing matrices of weight n. We also show that, for every odd prime power q, there are at most finitely many proper circulant weighing matrices of weight q.     

Repetition-free longest common subsequence

We study the following problem. Given two sequences x and y over a finite alphabet, find a repetition-free longest common subsequence of x and y. We show several algorithmic results, a computational complexity result, and we describe a preliminary experimental study based on the proposed algorithms. We also show that this problem is APX-hard.     

Convex equipartitions via Equivariant Obstruction Theory

We describe a regular cell complex model for the configuration space F(? ^d , n). Based on this, we use Equivariant Obstruction Theory to prove the prime power case of the conjecture by Nandakumar and Ramana Rao that every polygon can be partitioned into n convex parts of equal area and perimeter.     

The Gauss–Wilson theorem for quarter-intervals

We define a Gauss factorial N _n ! to be the product of all positive integers up to N that are relatively prime to n. It is the purpose of this paper to study the multiplicative orders of the Gauss factorials $\left\lfloor\frac{n-1}{4}\right\rfloor_{n}!$ for odd positive integers n. The case where n has exactly one prime factor of the form p≡1(mod4) is of particular interest, as will be explained in the introduction. A fundamental role is played by p with the property that the order of  $\frac{p-1}{4}!$ modulo p is a power of 2; because of their connection to two different results of Gauss we call them Gauss primes. Our main result is a complete characterization in terms of Gauss primes of those n of the above form that satisfy $\left\lfloor\frac{n-1}{4}\right\rfloor_{n}!\equiv 1\pmod{n}$ . We also report on computations that were required in the process.     

Correspondance de Jacquet-Langlands pour les corps locaux de caractéristique non nulle

In this article we prove the Jacquet-Langlands local correspondence in non-zero characteristic. Let F be a local field of non-zero charactersitic and G′ an inner form of GL_n(F); then, following [17], we prove relations between the representation theory of G′ and the representation theory of an inner form of GL_n(L), where L is a local field of zero characteristic close to F. The proof of the Jacquet-Langlands correspondence between G′ and GL_n(F) is done using the above results and ideas from the proof by Deligne, Kazhdan and Vignéras [10] of the zero characteristic case. We also get the following, already known in zero characteristic: orthogonality relations for G′, inequality involving conductor and level for representations of G′ and finiteness for automorphic cuspidal representations with fixed component at almost every place for an inner form of GL_n over a global field of non-zero characteristic.     

A family of quadriphase sequences of period 4(2 n − 1) with low correlation and large linear span

In this paper, a new family of quadriphase sequences with period 4(2 ⁿ ? 1) is proposed for n = me, where m is an odd integer. The correlation values of the family, their distribution, and the linear spans of the proposed sequences are completely determined under two situations.     

Sequences with constant number of return words

An infinite word has the property R _m if every factor has exactly m return words. Vuillon showed that R ₂ characterizes Sturmian words. We prove that a word satisfies R _m if its complexity function is (m ? 1)n + 1 and if it contains no weak bispecial factor. These conditions are necessary for m = 3, whereas for m = 4 the complexity function need not be 3n + 1. A new class of words satisfying R _m is given.     

Certain Contact Metrics as Ricci Almost Solitons

We show that if a compact K-contact metric is a gradient Ricci almost soliton, then it is isometric to a unit sphere S ²ⁿ⁺¹. Next, we prove that if the metric of a non-Sasakian (κ, μ)-contact metric is a gradient Ricci almost soliton, then in dimension 3 it is flat and in higher dimensions it is locally isometric to E ⁿ⁺¹ ×  S ⁿ (4). Finally, a couple of results on contact metric manifolds whose metric is a Ricci almost soliton and the potential vector field is point wise collinear with the Reeb vector field of the contact metric structure were obtained.     

Odd prime values of the Ramanujan tau function

We study the odd prime values of the Ramanujan tau function, which form a thin set of large primes. To this end, we define LR(p,n):=τ(p ^n?1) and we show that the odd prime values are of the form LR(p,q) where p,q are odd primes. Then we exhibit arithmetical properties and congruences of the LR numbers using more general results on Lucas sequences. Finally, we propose estimations and discuss numerical results on pairs (p,q) for which LR(p,q) is prime.     

Error linear complexity measures for multisequences

Complexity measures for sequences over finite fields, such as the linear complexity and the k-error linear complexity, play an important role in cryptology. Recent developments in stream ciphers point towards an interest in word-based stream ciphers, which require the study of the complexity of multisequences. We introduce various options for error linear complexity measures for multisequences. For finite multisequences as well as for periodic multisequences with prime period, we present formulas for the number of multisequences with given error linear complexity for several cases, and we present lower bounds for the expected error linear complexity.