A note on a problem of Brocard-Ramanujan

The Brocard-Ramanujan problem pertains to the Diophantine equation n!+1=m ². Using the quadratic reciprocity law, we prove the existence of many infinite families of positive integers n such that n!+1 is not a perfect square, and we give several simple criteria for n!+1 to be a non-square.      

<Emphasis Type="Italic">k</Emphasis>-Free-like groups

The following results are proved. In Theorem 1, it is stated that there exist both finitely presented and not finitely presented 2-generated nonfree groups which are k-free-like for any k ⩾ 2. In Theorem 2, it is claimed that every nonvirtually cyclic (resp., noncyclic and torsion-free) hyperbolic m-generated group is k-free-like for every k ⩾ m + 1 (resp., k ⩾ m). Finally, Theorem 3 asserts that there exists a 2-generated periodic group G which is k-free-like for every k ⩾ 3. Supported by NSF (grant Nos. DMS 0455881 and DMS-0700811). (A. Yu. Olshanskii, M. V. Sapir) Supported by RFBR project No. 08-01-00573. (A. Yu. Olshanskii) Supported by BSF grant (USA–Israel). (M. V. Sapir) Translated from Algebra i Logika, Vol. 48, No. 2, pp. 245–257, March–April, 2009.     

Reliability formula &; limit law of the failure time of “<Emphasis Type="Italic">m</Emphasis>-consecutive-<Emphasis Type="Italic">k</Emphasis>-out-of-<Emphasis Type="Italic">n</Emphasis>:<Emphasis Type="Italic">F</Emphasis> system”

An “m-consecutive-k-out-of-n:F system” consists of n components ordered on a line; the system fails if and only if there are at least m nonoverlapping runs of k consecutive failed components. In this paper, we give a recursive formula to compute the reliability of such a system. Thereafter, we state two asymptotic results concerning the failure time Z _n of the system. The first result concerns a limit theorem for Z _n when the failure times of components are not necessarily with identical failure distributions. In the second one, we prove that, for an arbitrary common failure distribution of components, the limit system failure distribution is always of the Poisson class.      

Tight sets,weighted <Emphasis Type="Italic">m</Emphasis>-covers,weighted <Emphasis Type="Italic">m</Emphasis>-ovoids,and minihypers

Minihypers are substructures of projective spaces introduced to study linear codes meeting the Griesmer bound. Recently, many results in finite geometry were obtained by applying characterization results on minihypers (De Beule et al. 16:342–349, 2008; Govaerts and Storme 4:279–286, 2004; Govaerts et al. 28:659–672, 2002). In this paper, using characterization results on certain minihypers, we present new results on tight sets in classical finite polar spaces and weighted m-covers, and on weighted m-ovoids of classical finite generalized quadrangles. The link with minihypers gives us characterization results of i-tight sets in terms of generators and Baer subgeometries contained in the Hermitian and symplectic polar spaces, and in terms of generators for the quadratic polar spaces. We also present extendability results on partial weighted m-ovoids and partial weighted m-covers, having small deficiency, to weighted m-covers and weighted m-ovoids of classical finite generalized quadrangles. As a particular application, we prove in an alternative way the extendability of 53-, 54-, and 55-caps of PG(5,3), contained in a non-singular elliptic quadric Q⁻(5,3), to 56-caps contained in this elliptic quadric Q⁻(5,3).      

On the Order of Convergence of a Determinantal Family of Root-Finding Methods

Recently, we have shown that for each natural number m greater than one, and each natural number k less than or equal to m, there exists a root-finding iteration function, defined as the ratio of two determinants that depend on the first m - k derivatives of the given function. For each k the corresponding matrices are upper Hessenberg matrices. Additionally, for k = 1 these matrices are Toeplitz matrices. The goal of this paper is to analyze the order of convergence of this fundamental family. Newton's method, Halley's method, and their multi-point versions are members of this family. In this paper we also derive these special cases. We prove that for fixed m, as k increases, the order of convergence decreases from m to the positive root of the characteristic polynomial of generalized Fibonacci numbers of order m. For fixed k, the order of convergence increases in m. The asymptotic error constant is also derived in terms of special determinants.     

On the number of conjugacy classes of finite nilpotent groups

We establish the first super-logarithmic lower bound for the number of conjugacy classes of a finite nilpotent group. In particular, we obtain that for any constant c there are only finitely many finite p-groups of order pm with at most c⋅m conjugacy classes. This answers a question of L. Pyber.     

On the inverse problem relative to dynamics of the <Emphasis Type="Italic">w</Emphasis> function

Let P be the set of prime numbers and P(n) denote the largest prime factor of integer n > 1. Write

NP-completeness conditions for consistency verification of some types of systems of linear Diophantine dis-equations

Three series of number-theoretic problems with explicitly defined parameters concerning systems of Diophantine dis-equations with solutions from a given domain are considered. Constraints on these parameters under which any problem of each series is NP-complete are proved. It is proved that for any m and m′ (m < m′) the consistency problem on the segment [m, m′] for a system of linear Diophantine dis-equations, each of which contains exactly three variables (even if the coefficients at these variables belong to {–1, 1}), is NP-complete. This problem admits a simple geometric interpretation of NP-completeness for the determination of whether there exists an integer-valued point inside a multidimensional cube that is not covered by given hyperplanes that cut off equal segments on three arbitrary axes and are parallel to all other axes. If in a system of linear Diophantine dis-equations each dis-equation contains exactly two variables, the problem remains NP-complete under the condition that the following inequality holds: m′–m > 2. It is also proved that if the solution to a system of linear Diophantine dis-equations, each containing exactly three variables, is sought in the domain given by a system of polynomial inequalities that contain an n-dimensional cube and are contained in an n-dimensional parallelepiped symmetric with respect to the point of origin, its consistency problem is NP-complete.     

Sparse <Emphasis Type="Italic">H</Emphasis>-Colourable Graphs of Bounded Maximum Degree

Let F be a graph of order at most k. We prove that for any integer g there is a graph G of girth at least g and of maximum degree at most 5k¹³ such that G admits a surjective homomorphism c to F, and moreover, for any F-pointed graph H with at most k vertices, and for any homomorphism h from G to H there is a unique homomorphism f from F to H such that h=fc. As a consequence, we prove that if H is a projective graph of order k, then for any finite family of prescribed mappings from a set X to V(H) (with ||=t), there is a graph G of arbitrary large girth and of maximum degree at most 5k^26mt (where m=|X|) such that and up to an automorphism of H, there are exactly t homomorphisms from G to H, each of which is an extension of an f.Supported in part by the National Science Council under grant NSC89-2115-M-110-012Final version received: June 9, 2003     

Zur simultanen Diophantischen Approximation. I

An important problem in the field of Diophantine Approximation was solved in 1891 byHurwitz. He could show that any irrational number can be approximated by infinitely many rationals in such a way that the modulus of the difference multiplied with the square of the denominator is less than 5^–1/2, and there 5^–1/2 is best possible.-The generalization of this problem in the direction of simultaneous Diophantine Approximation is still unsolved.Furtwängler in 1925 gave lower bounds for the maximum difference, conjecturing that these were best possible.-Here it is shown that in the two dimensional caseFurtwängler's bounds are indeed best possible for certain irrationals lying in cubic number fields which are not totally real. Yet by considering totally real cubic fields we are led to replaceFurtwängler's conjecture by a new one.     

On the non-existence of barker sequences

It is an old conjecture that there are no unknown Barker sequences. Here, a sufficient condition for the non-existence of Barker sequences of even length 4m ² is given, which allows us to show that there are no unknown sequences withm less than 105, exceptm=63, which remains still undecided.     

Realization of Configurations and the Löwner Ellipsoid

It is proved that any subset of an (m-1)-dimensional sphere of volume larger than l(m+ 1) of the volume of the entire sphere contains l+ 1 points forming a regular l-dimensional simplex. As a corollary, it is obtained that, if the exterior of a given m-dimensional filled ellipsoid contains no more than the 1/(m+ 1) fraction of some sphere, then the volume of the ellipsoid is no less than the volume of the corresponding ball. The existence of a pair of points a given spherical distance apart in a set of positive measure is examined.     

Exact <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">2</Emphasis></Subscript>-small ball behavior of integrated Gaussian processes and spectral asymptotics of boundary value problems

We find the exact small deviation asymptotics for the L₂-norm of various m-times integrated Gaussian processes closely connected with the Wiener process and the Ornstein – Uhlenbeck process. Using a general approach from the spectral theory of linear differential operators we obtain the two-term spectral asymptotics of eigenvalues in corresponding boundary value problems. This enables us to improve the recent results from [15] on the small ball asymptotics for a class of m-times integrated Wiener processes. Moreover, the exact small ball asymptotics for the m-times integrated Brownian bridge, the m-times integrated Ornstein – Uhlenbeck process and similar processes appear as relatively simple examples illustrating the developed general theory.Partially supported by grants of RFBR 01-01-00245 and 02-01-01099.     

Integral representation for powers of elements in locally <Emphasis Type="Italic">m</Emphasis>-convex algebras and applications

This paper proves a new integral representation theorem for powers of elements in locally m-convex algebras. It is shown that the conditions handled in this theorem are satisfied for any sequentially complete locally m-convex Q-algebra. Various applications of this result concerning the spectrum, the spectral radius or the numerical radius are given.      

<Emphasis Type="Italic">k</Emphasis>-factors in regular graphs

Plesnik in 1972 proved that an （m - 1）-edge connected m-regular graph of even order has a 1-factor containing any given edge and has another 1-factor excluding any given m - 1 edges. Alder et al. in 1999 showed that if G is a regular （2n ＋ 1）-edge-connected bipartite graph, then G has a 1-factor containing any given edge and excluding any given matching of size n. In this paper we obtain some sufficient conditions related to the edge-connectivity for an n-regular graph to have a k-factor containing a set of edges and （or） excluding a set of edges, where 1 ≤ k ≤n/2. In particular, we generalize Plesnik＇s result and the results obtained by Liu et al. in 1998, and improve Katerinis＇ result obtained 1993. Furthermore, we show that the results in this paper are the best possible.     

Paranorm <Emphasis Type="Italic">I</Emphasis>-convergent sequence spaces

In this article we introduced the sequence spaces c ^I (p), c ₀ ^I (p), m ^I (p) and m ₀ ^I (p) for p = (p _k ), a sequence of positive real numbers. We study some algebraic and topological properties of these spaces. We prove the decomposition theorem and obtain some inclusion relations.      

A construction of binary Golay sequence pairs from odd‐length Barker sequences

Binary Golay sequence pairs exist for lengths 2, 10 and 26 and, by Turyn's product construction, for all lengths of the form 2^a10^b26^c where a, b, c are non‐negative integers. Computer search has shown that all inequivalent binary Golay sequence pairs of length less than 100 can be constructed from five “seed” pairs, of length 2, 10, 10, 20 and 26. We give the first complete explanation of the origin of the length 26 binary Golay seed pair, involving a Barker sequence of length 13 and a related Barker sequence of length 11. This is the special case m=1 of a general construction for a length 16m+10 binary Golay pair from a related pair of Barker sequences of length 8m+5 and 8m+3, for integer m≥0. In the case m=0, we obtain an alternative explanation of the origin of one of the length 10 binary Golay seed pairs. The construction cannot produce binary Golay sequence pairs for m>1, having length greater than 26, because there are no Barker sequences of odd length greater than 13. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 478–491, 2009     

On <Emphasis Type="Italic">n</Emphasis> × <Emphasis Type="Italic">m</Emphasis>-valued Łukasiewicz-Moisil algebras

n×m-valued Łukasiewicz algebras with negation were introduced and investigated in [20, 22, 23]. These algebras constitute a non trivial generalization of n-valued Łukasiewicz-Moisil algebras and in what follows, we shall call them n×m-valued Łukasiewicz-Moisil algebras (or LM _n×m -algebras). In this paper, the study of this new class of algebras is continued. More precisely, a topological duality for these algebras is described and a characterization of LM _n×m -congruences in terms of special subsets of the associated space is shown. Besides, it is determined which of these subsets correspond to principal congruences. In addition, it is proved that the variety of LM _n×m -algebras is a discriminator variety and as a consequence, certain properties of the congruences are obtained. Finally, the number of congruences of a finite LM _n×m -algebra is computed.      

A construction of an infinite family of 2-arc transitive polygonal graphs of arbitrary even girth

A near-polygonal graph is a graph Γ which has a set C\mathcal{C} of m-cycles for some positive integer m such that each 2-path of Γ is contained in exactly one cycle in C\mathcal{C}. If m is the girth of Γ, then the graph is called polygonal. We provide a construction of an infinite family of polygonal graphs of arbitrary even girth with 2-arc transitive automorphism groups, showing that there are infinitely many 2-arc transitive polygonal graphs of every girth.     

Improvement of an estimate of H. Müller involving the order of 2(mod u) II

Let m≧ 1 be an arbitrary fixed integer and let N_m(x) count the number of odd integers u≦ x such that the order of 2 modulo u is not divisible by m. In case m is prime, estimates for N_m (x) were given by Müller that were subsequently sharpened into an asymptotic estimate by the present author. Müller on his turn extended the author’s result to the case where m is a prime power and gave bounds in the case m is not a prime power. Here an asymptotic for N_m (x) is derived that is valid for all integers m. We also generalize to other base numbers than 2. A further analysis of Müller’s method leads us to study and solve a certain Diophantine equation. Received: 23 August 2005