Interassociates of the bicyclic semigroup

An interassociate of a semigroup \((S,\cdot )\) is a semigroup \((S, *)\) such that for all \(a, b, c \in S\), \(a\cdot (b*c)=(a\cdot b) *c\) and \(a*(b\cdot c)=(a*b) \cdot c\). We investigate the bicyclic semigroup C and its interassociates. In particular, if p and q are the generators of the bicyclic semigroup and m and n are fixed nonnegative integers, the operation \(a*_{m,n} b= aq^mp^n b\) is known to be an interassociate. We show that for distinct pairs (m, n) and (s, t), the interassociates \((C, *_{m,n})\) and \((C, *_{s,t})\) are not isomorphic. We also generalize a result regarding homomorphisms on C to homomorphisms on its interassociates.     

Universal Cycle Packings and Coverings for <Emphasis Type="Italic">k</Emphasis>-Subsets of an <Emphasis Type="Italic">n</Emphasis>-Set

A cyclic sequence of elements of [n] is an (n, k)-Ucycle packing (respectively, (n, k)-Ucycle covering) if every k-subset of [n] appears in this sequence at most once (resp. at least once) as a subsequence of consecutive terms. Let \(p_{n,k}\) be the length of a longest (n, k)-Ucycle packing and \(c_{n,k}\) the length of a shortest (n, k)-Ucycle covering. We show that, for a fixed \(k,p_{n,k}={n\atopwithdelims ()k}-O(n^{\lfloor k/2\rfloor })\). Moreover, when k is not fixed, we prove that if \(k=k(n)\le n^{\alpha }\), where \(0<\alpha <1/3\), then \(p_{n,k}={n\atopwithdelims ()k}-o({n\atopwithdelims ()k}^\beta )\) and \(c_{n,k}={n\atopwithdelims ()k}+o({n\atopwithdelims ()k}^\beta )\), for some \(\beta <1\). Finally, we show that if \(k=o(n)\), then \(p_{n,k}={n\atopwithdelims ()k}(1-o(1))\).     

Optimal Order Quadrature Error Bounds for Infinite-Dimensional Higher-Order Digital Sequences

Quasi-Monte Carlo (QMC) quadrature rules using higher-order digital nets and sequences have been shown to achieve the almost optimal rate of convergence of the worst-case error in Sobolev spaces of arbitrary fixed smoothness \(\alpha \in \mathbb {N}\), \(\alpha \ge 2\). In a recent paper by the authors, it was proved that randomly digitally shifted order \(2\alpha \) digital nets in prime base b achieve the best possible rate of convergence of the root mean square worst-case error of order \(N^{-\alpha }(\log N)^{(s-1)/2}\) for \(N=b^m\), where N and s denote the number of points and the dimension, respectively, which implies the existence of an optimal order QMC rule. More recently, the authors provided an explicit construction of such an optimal order QMC rule by using Chen–Skriganov’s digital nets in conjunction with Dick’s digit interlacing composition. These results were for fixed number of points. In this paper, we give a more general result on an explicit construction of optimal order QMC rules for arbitrary fixed smoothness \(\alpha \in \mathbb {N}\) including the endpoint case \(\alpha =1\). That is, we prove that the projection of any infinite-dimensional order \(2\alpha +1\) digital sequence in prime base b onto the first s coordinates achieves the best possible rate of convergence of the worst-case error of order \(N^{-\alpha }(\log N)^{(s-1)/2}\) for \(N=b^m\). The explicit construction presented in this paper is not only easy to implement but also extensible in both N and s.     

Few associative triples,isotopisms and groups

Let Q be a quasigroup. For \(\alpha ,\beta \in S_Q\) let \(Q_{\alpha ,\beta }\) be the principal isotope \(x*y = \alpha (x)\beta (y)\). Put \(\mathbf a(Q)= |\{(x,y,z)\in Q^3;\) \(x(yz)) = (xy)z\}|\) and assume that \(|Q|=n\). Then \(\sum _{\alpha ,\beta }\mathbf a(Q_{\alpha ,\beta })/(n!)^2 = n^2(1+(n-1)^{-1})\), and for every \(\alpha \in S_Q\) there is \(\sum _\beta \mathbf a(Q_{\alpha ,\beta })/n! = n(n-1)^{-1}\sum _x(f_x^2-2f_x+n)\ge n^2\), where \(f_x=|\{y\in Q;\) \( y = \alpha (y)x\}|\). If G is a group and \(\alpha \) is an orthomorphism, then \(\mathbf a(G_{\alpha ,\beta })=n^2\) for every \(\beta \in S_Q\). A detailed case study of \(\mathbf a(G_{\alpha ,\beta })\) is made for the situation when \(G = \mathbb Z_{2d}\), and both \(\alpha \) and \(\beta \) are “natural” near-orthomorphisms. Asymptotically, \(\mathbf a(G_{\alpha ,\beta })>3n\) if G is an abelian group of order n. Computational results: \(\mathbf a(7) = 17\) and \(\mathbf a(8) \le 21\), where \(\mathbf a(n) = \min \{\mathbf a(Q);\) \( |Q|=n\}\). There are also determined minimum values for \(\mathbf a(G_{\alpha ,\beta })\), G a group of order \(\le 8\).     

Iterated local search with Trellis-neighborhood for the partial Latin square extension problem

A partial Latin square (PLS) is a partial assignment of n symbols to an \(n\times n\) grid such that, in each row and in each column, each symbol appears at most once. The PLS extension problem is an NP-hard problem that asks for a largest extension of a given PLS. We consider the local search such that the neighborhood is defined by (p, q)-swap , i.e., the operation of dropping exactly p symbols and then assigning symbols to at most q empty cells. As a fundamental result, we provide an efficient \((p,\infty )\)-neighborhood search algorithm that finds an improved solution or concludes that no such solution exists for \(p\in \{1,2,3\}\). The running time of the algorithm is \(O(n^{p+1})\). We then propose a novel swap operation, Trellis-swap, which is a generalization of (p, q)-swap with \(p\le 2\). The proposed Trellis-neighborhood search algorithm runs in \(O(n^{3.5})\) time. The iterated local search (ILS) algorithm with Trellis-neighborhood is more likely to deliver a high-quality solution than not only ILSs with \((p,\infty )\)-neighborhood but also state-of-the-art optimization solvers such as IBM ILOG CPLEX and LocalSolver.     

On the optimal order of worst case complexity of direct search

The worst case complexity of direct-search methods has been recently analyzed when they use positive spanning sets and impose a sufficient decrease condition to accept new iterates. For smooth unconstrained optimization, it is now known that such methods require at most \(\mathcal {O}(n^2\epsilon ^{-2})\) function evaluations to compute a gradient of norm below \(\epsilon \in (0,1)\), where n is the dimension of the problem. Such a maximal effort is reduced to \(\mathcal {O}(n^2\epsilon ^{-1})\) if the function is convex. The factor \(n^2\) has been derived using the positive spanning set formed by the coordinate vectors and their negatives at all iterations. In this paper, we prove that such a factor of \(n^2\) is optimal in these worst case complexity bounds, in the sense that no other positive spanning set will yield a better order of n. The proof is based on an observation that reveals the connection between cosine measure in positive spanning and sphere covering.     

Map determined by rank-$$\varvec{}$$ matrice for relatively mall $$\varvec{}$$

Let n and s be integers such that \(1\le s<\frac{n}{2}\), and let \(M_n(\mathbb {K})\) be the ring of all \(n\times n\) matrices over a field \(\mathbb {K}\). Denote by \([\frac{n}{s}]\) the least integer m with \(m\ge \frac{n}{s}\). In this short note, it is proved that if \(g:M_n(\mathbb {K})\rightarrow M_n(\mathbb {K})\) is a map such that \(g\left( \sum _{i=1}^{[\frac{n}{s}]}A_i\right) =\sum _{i=1}^{[\frac{n}{s}]}g(A_i)\) holds for any \([\frac{n}{s}]\) rank-s matrices \(A_1,\ldots ,A_{[\frac{n}{s}]}\in M_n(\mathbb {K})\), then \(g(x)=f(x)+g(0)\), \(x\in M_n(\mathbb {K})\), for some additive map \(f:M_n(\mathbb {K})\rightarrow M_n(\mathbb {K})\). Particularly, g is additive if \(char\mathbb {K}\not \mid \left( [\frac{n}{s}]-1\right) \).     

A Tight Upper Bound on Acquaintance Time of Graphs

In this note we confirm a conjecture raised by Benjamini et al. (SIAM J Discrete Math 28(2):767–785, 2014) on the acquaintance time of graphs, proving that for all graphs G with n vertices it holds that \(\mathcal {AC}(G) = O(n^{3/2})\). This is done by proving that for all graphs G with n vertices and maximum degree \(\varDelta \) it holds that \(\mathcal {AC}(G) \le 20 \varDelta n\). Combining this with the bound \(\mathcal {AC}(G) \le O(n^2/\varDelta )\) from Benjamini et al. (SIAM J Discrete Math 28(2):767–785, 2014) gives the uniform upper bound of \(O(n^{3/2})\) for all n-vertex graphs. This bound is tight up to a multiplicative constant. We also prove that for the n-vertex path \(P_n\) it holds that \(\mathcal {AC}(P_n)=n-2\). In addition we show that the barbell graph \(B_n\) consisting of two cliques of sizes \({\lceil n/2\rceil }\) and \({\lfloor n/2\rfloor }\) connected by a single edge also has \(\mathcal {AC}(B_n) = n-2\). This shows that it is possible to add \(\varOmega (n^2\)) edges a graph without changing its \(\mathcal {AC}\) value.     

Critical Sets of Full <Emphasis Type="Italic">n</Emphasis>-Latin Squares

The full n-Latin square is the \(n\times n\) array with symbols \(1,2,\dots ,n\) in each cell. In a way that is analogous to critical sets of full designs, a critical set of the full n-Latin square can be used to find a defining set for any Latin square of order n. In this paper we study the size of the smallest critical set for a full n-Latin square, showing this to be somewhere between \((n^3-2n^2+2n)/2\) and \((n-1)^3+1\). In the case that each cell is either full or empty, we show the size of a critical set in the full n-Latin square is always equal to \(n^3-2n^2-n\).     

On the family of elliptic curves $$\varvec{y^2=x^3-m^2x+p^2}$$

In this paper, we study the torsion subgroup and rank of elliptic curves for the subfamilies of \(E_{m,p} : y^2=x^3-m^2x+p^2\), where m is a positive integer and p is a prime. We prove that for any prime p, the torsion subgroup of \(E_{m,p}(\mathbb {Q})\) is trivial for both the cases {\(m\ge 1\), \(m\not \equiv 0\pmod 3\)} and {\(m\ge 1\), \(m \equiv 0 \pmod 3\), with \(gcd(m,p)=1\)}. We also show that given any odd prime p and for any positive integer m with \(m\not \equiv 0\pmod 3\) and \(m\equiv 2\pmod {32}\), the lower bound for the rank of \(E_{m,p}(\mathbb {Q})\) is 2. Finally, we find curves of rank 9 in this family.     

Approximation by Polynomials in Sobolev Spaces with Jacobi Weight

Polynomial approximation is studied in the Sobolev space \(W_p^r(w_{\alpha ,\beta })\) that consists of functions whose r-th derivatives are in weighted \(L^p\) space with the Jacobi weight function \(w_{\alpha ,\beta }\). This requires simultaneous approximation of a function and its consecutive derivatives up to s-th order with \(s \le r\). We provide sharp error estimates given in terms of \(E_n(f^{(r)})_{L^p(w_{\alpha ,\beta })}\), the error of best approximation to \(f^{(r)}\) by polynomials in \(L^p(w_{\alpha ,\beta })\), and an explicit construction of the polynomials that approximate simultaneously with the sharp error estimates.     

Coloring Complete and Complete Bipartite Graphs from Random Lists

Assign to each vertex v of the complete graph \(K_n\) on n vertices a list L(v) of colors by choosing each list independently and uniformly at random from all f(n)-subsets of a color set \([n] = \{1,\dots , n\}\), where f(n) is some integer-valued function of n. Such a list assignment L is called a random (f(n), [n])-list assignment. In this paper, we determine the asymptotic probability (as \(n \rightarrow \infty \)) of the existence of a proper coloring \(\varphi \) of \(K_n\), such that \(\varphi (v) \in L(v)\) for every vertex v of \(K_n\). We show that this property exhibits a sharp threshold at \(f(n) = \log n\). Additionally, we consider the corresponding problem for the line graph of a complete bipartite graph \(K_{m,n}\) with parts of size m and n, respectively. We show that if \(m = o(\sqrt{n})\), \(f(n) \ge 2 \log n\), and L is a random (f(n), [n])-list assignment for the line graph of \(K_{m,n}\), then with probability tending to 1, as \(n \rightarrow \infty \), there is a proper coloring of the line graph of \(K_{m,n}\) with colors from the lists.     

Tightness and Convergence of Trimmed Lévy Processes to Normality at Small Times

For nonnegative integers r, s, let \(^{(r,s)}X_t\) be the Lévy process \(X_t\) with the r largest positive jumps and the s smallest negative jumps up till time t deleted, and let \(^{(r)}\widetilde{X}_t\) be \(X_t\) with the r largest jumps in modulus up till time t deleted. Let \(a_t \in \mathbb {R}\) and \(b_t>0\) be non-stochastic functions in t. We show that the tightness of \(({}^{(r,s)}X_t - a_t)/b_t\) or \(({}^{(r)}{\widetilde{X}}_t - a_t)/b_t\) as \(t\downarrow 0\) implies the tightness of all normed ordered jumps, and hence the tightness of the untrimmed process \((X_t -a_t)/b_t\) at 0. We use this to deduce that the trimmed process \(({}^{(r,s)}X_t - a_t)/b_t\) or \(({}^{(r)}{\widetilde{X}}_t - a_t)/b_t\) converges to N(0, 1) or to a degenerate distribution as \(t\downarrow 0\) if and only if \((X_t-a_t)/b_t \) converges to N(0, 1) or to the same degenerate distribution, as \(t \downarrow 0\).     

Normal forms under Simon’s congruence

Simon’s congruence, denoted by \(\sim _k\), relates the words having the same subwords of length at most k. In this paper a normal form is presented for the equivalence classes of \(\sim _k\). The length of this normal form is the shortest possible. Moreover, a canonical solution of the equation \(pwq\sim _k r\) is also shown (the words p, q, r are parameters), which can be viewed as a generalization of giving a normal form for \(\sim _k\). In this paper, there can be found an algorithm with which the canonical solution can be determined in \(O((L+n)n^{k})\) time, where L denotes the length of the word pqr and n is the size of the alphabet.     

On the gaps between non-zero Fourier coefficients of cusp forms of higher weight

We show that if a modular cuspidal eigenform f of weight 2k is 2-adically close to an elliptic curve \(E/\mathbb {Q}\), which has a cyclic rational 4-isogeny, then n-th Fourier coefficient of f is non-zero in the short interval \((X, X + cX^{\frac{1}{4}})\) for all \(X \gg 0\) and for some \(c > 0\). We use this fact to produce non-CM cuspidal eigenforms f of level \(N>1\) and weight \(k > 2\) such that \(i_f(n) \ll n^{\frac{1}{4}}\) for all \(n \gg 0\).     

Newly appointed editors

Let k be a field and \(k(x_0,\ldots ,x_{p-1})\) be the rational function field of p variables over k where p is a prime number. Suppose that \(G=\langle \sigma \rangle \simeq C_p\) acts on \(k(x_0,\ldots ,x_{p-1})\) by k-automorphisms defined as \(\sigma :x_0\mapsto x_1\mapsto \cdots \mapsto x_{p-1}\mapsto x_0\). Denote by P the set of all prime numbers and define \(P_0=\{p\in P:\mathbb {Q}(\zeta _{p-1})\) is of class number one\(\}\) where \(\zeta _n\) a primitive n-th root of unity in \(\mathbb {C}\) for a positive integer n; \(P_0\) is a finite set by Masley and Montgomery (J Reine Angew Math 286/287:248–256, 1976). Theorem. Let k be an algebraic number field and \(P_k=\{p\in P: p\) is ramified in \(k\}\). Then \(k(x_0,\ldots ,x_{p-1})^G\) is not stably rational over k for all \(p\in P\backslash (P_0\cup P_k)\).     

Partial permutation decoding for binary linear and $$Z_4$$-linear Hadamard codes

In this paper, s-\({\text {PD}}\)-sets of minimum size \(s+1\) for partial permutation decoding for the binary linear Hadamard code \(H_m\) of length \(2^m\), for all \(m\ge 4\) and \(2 \le s \le \lfloor {\frac{2^m}{1+m}}\rfloor -1\), are constructed. Moreover, recursive constructions to obtain s-\({\text {PD}}\)-sets of size \(l\ge s+1\) for \(H_{m+1}\) of length \(2^{m+1}\), from an s-\({\text {PD}}\)-set of the same size for \(H_m\), are also described. These results are generalized to find s-\({\text {PD}}\)-sets for the \({\mathbb {Z}}_4\)-linear Hadamard codes \(H_{\gamma , \delta }\) of length \(2^m\), \(m=\gamma +2\delta -1\), which are binary Hadamard codes (not necessarily linear) obtained as the Gray map image of quaternary linear codes of type \(2^\gamma 4^\delta \). Specifically, s-PD-sets of minimum size \(s+1\) for \(H_{\gamma , \delta }\), for all \(\delta \ge 3\) and \(2\le s \le \lfloor {\frac{2^{2\delta -2}}{\delta }}\rfloor -1\), are constructed and recursive constructions are described.     

Multi-player Last Nim with Passes

We introduce a class of impartial combinatorial games, Multi-player Last Nim with Passes, denoted by MLNim\(^{(s)}(N,n)\): there are N piles of counters which are linearly ordered. In turn, each of n players either removes any positive integer of counters from the last pile, or makes a choice ‘pass’. Once a ‘pass’ option is used, the total number s of passes decreases by 1. When all s passes are used, no player may ever ‘pass’ again. A pass option can be used at any time, up to the penultimate move, but cannot be used at the end of the game. The player who cannot make a move wins the game. The aim is to determine the game values of the positions of MLNim\(^{(s)}(N,n)\) for all integers \(N\ge 1\) and \(n\ge 3\) and \(s\ge 1\). For \(n>N+1\) or \(n=N+1\ge 3\), the game values are completely determined for any \(s\ge 1\). For \(3\le n\le N\), the game values are determined for infinitely many triplets (N, n, s). We also present a possible explanation why determining the game values becomes more complicated if \(n\le N\).     

Some results on a special case of a general continued fraction of Ramanujan

We derive a new special case C(q) of a general continued fraction recorded by Ramanujan in his Lost Notebook. We give a representation of the continued fraction C(q) as a quotient of Dedekind eta-function and then use it to prove modular identities connecting C(q) with each of the continued fractions \(C(-q)\), \(C(q^{2})\), \(C(q^{3})\), \(C(q^{5})\), \(C(q^{7})\), \(C(q^{11})\), \(C(q^{13})\) and \(C(q^{17})\). We also prove general theorems for the explicit evaluation of the continued fraction C(q) by using Ramanujan’s class invariants.     

Connected size Ramsey number for matchings vs. small stars or cycles

The notation \(F\rightarrow (G,H)\) means that if the edges of F are colored red and blue, then the red subgraph contains a copy of G or the blue subgraph contains a copy of H. The connected size Ramsey number \(\hat{r}_c(G,H)\) of graphs G and H is the minimum size of a connected graph F satisfying \(F\rightarrow (G,H)\). For \(m \ge 2,\) the graph consisting of m independent edges is called a matching and is denoted by \(mK_2\). In 1981, Erdös and Faudree determined the size Ramsey numbers for the pair \((mK_2, K_{1,t})\). They showed that the disconnected graph \(mK_{1,t} \rightarrow (mK_2,K_{1,t})\) for \( t,m \ge 1\). In this paper, we will determine the connected size Ramsey number \(\hat{r}_c(nK_2, K_{1,3})\) for \(n\ge 2\) and \(\hat{r}_c(3K_2, C_4)\). We also derive an upper bound of the connected size Ramsey number \(\hat{r}_c(nK_2, C_4),\) for \(n\ge 4\).