An Engel condition with skew derivations for one-sided ideals

We apply the theory of generalized polynomial identities with automorphisms and skew derivations to prove the following theorem: Let A be a prime ring with the extended centroid C and with two-sided Martindale quotient ring Q, R a nonzero right ideal of A and \(\delta \) a nonzero \(\sigma \)-derivation of A, where \(\sigma \) is an epimorphism of A. For \(x,y\in A\), we set \([x,y] = xy - yx\). If \([[\ldots [[\delta (x^{n_0}),x^{n_1}],x^{n_{2}}],\ldots ],x^{n_k}]=0\) for all \(x\in R\), where \(n_{0},n_{1},\ldots ,n_{k}\) are fixed positive integers, then one of the following conditions holds: (1) A is commutative; (2) \(C\cong GF(2)\), the Galois field of two elements; (3) there exist \(b\in Q\) and \(\lambda \in C\) such that \(\delta (x)=\sigma (x)b-bx\) for all \(x\in A\), \((b-\lambda )R=0\) and \(\sigma (R)=0\). The analogous result for left ideals is also obtained. Our theorems are natural generalizations of the well-known results for derivations obtained by Lanski (Proc Am Math Soc 125:339–345, 1997) and Lee (Can Math Bull 38:445–449, 1995).     

The primitive idempotents and weight distributions of irreducible constacyclic codes

Let \({\mathbb {F}}_q\) be a finite field with q elements such that \(l^v||(q^t-1)\) and \(\gcd (l,q(q-1))=1\), where l, t are primes and v is a positive integer. In this paper, we give all primitive idempotents in a ring \(\mathbb F_q[x]/\langle x^{l^m}-a\rangle \) for \(a\in {\mathbb {F}}_q^*\). Specially for \(t=2\), we give the weight distributions of all irreducible constacyclic codes and their dual codes of length \(l^m\) over \({\mathbb {F}}_q\).     

Approximation algorithms for constructing spanning K-trees using stock pieces of bounded length

Given a weighted graph G on \(n + 1\) vertices, a spanning K-tree \(T_K\) of G is defined to be a spanning tree T of G together with K distinct edges of G that are not edges of T. The objective of the minimum-cost spanning K-tree problem is to choose a subset of edges to form a spanning K-tree with the minimum weight. In this paper, we consider the constructing spanning K-tree problem that is a generalization of the minimum-cost spanning K-tree problem. We are required to construct a spanning K-tree \(T_K\) whose \(n+K\) edges are assembled from some stock pieces of bounded length L. Let \(c_0\) be the sale price of each stock piece of length L and \(k(T_K)\) the number of minimum stock pieces to construct the \(n+K\) edges in \(T_K\). For each edge e in G, let c(e) be the construction cost of that edge e. Our new objective is to minimize the total cost of constructing a spanning K-tree \(T_K\), i.e., \(\min _{T_K}\{\sum _{e\in T_K} c(e)+ k(T_K)\cdot c_0\}\). The main results obtained in this paper are as follows. (1) A 2-approximation algorithm to solve the constructing spanning K-tree problem. (2) A \(\frac{3}{2}\)-approximation algorithm to solve the special case for constant construction cost of edges. (3) An APTAS for this special case.     

A group of continuous self-maps on a topological groupoid

The group of bisections of groupoids plays an important role in the study of Lie groupoids. In this paper another construction is introduced. Indeed, for a topological groupoid G, the set of all continuous self-maps f on G such that (x, f(x)) is a composable pair for every \(x\in G\), is denoted by \(S_G\). We show that \(S_G\) by a natural binary operation is a monoid. \(S_G(\alpha )\), the group of units in \(S_G\) precisely consists of those \(f\in S_G\) such that the map \(x\mapsto xf(x)\) is a bijection on G. Similar to the group of bisections, \(S_G(\alpha )\) acts on G from the right and on the space of continuous self-maps on G from the left. It is proved that \(S_G(\alpha )\) with the compact- open topology inherited from C(G, G) is a left topological group. For a compact Hausdorff groupoid G it is proved that the group of bisections of \(G^2\) is isomorphic to the group \(S_G(\alpha )\) and the group of transitive bisections of G, \(Bis_T(G)\), is embedded in \(S_G(\alpha )\), where \(G^2\) is the groupoid of all composable pairs.     

Semidefinite bounds for nonbinary codes based on quadruples

For nonnegative integers q, n, d, let \(A_q(n,d)\) denote the maximum cardinality of a code of length n over an alphabet [q] with q letters and with minimum distance at least d. We consider the following upper bound on \(A_q(n,d)\). For any k, let \(\mathcal{C}_k\) be the collection of codes of cardinality at most k. Then \(A_q(n,d)\) is at most the maximum value of \(\sum _{v\in [q]^n}x(\{v\})\), where x is a function \(\mathcal{C}_4\rightarrow {\mathbb {R}}_+\) such that \(x(\emptyset )=1\) and \(x(C)=\!0\) if C has minimum distance less than d, and such that the \(\mathcal{C}_2\times \mathcal{C}_2\) matrix \((x(C\cup C'))_{C,C'\in \mathcal{C}_2}\) is positive semidefinite. By the symmetry of the problem, we can apply representation theory to reduce the problem to a semidefinite programming problem with order bounded by a polynomial in n. It yields the new upper bounds \(A_4(6,3)\le 176\), \(A_4(7,3)\le 596\), \(A_4(7,4)\le 155\), \(A_5(7,4)\le 489\), and \(A_5(7,5)\le 87\).     

The Terwilliger algebra of the incidence graph of the Hamming graph

Let \(\varGamma \) be a distance-semiregular graph on Y, and let \(D^Y\) be the diameter of \(\varGamma \) on Y. Let \(\varDelta \) be the halved graph of \(\varGamma \) on Y. Fix \(x \in Y\). Let T and \(T'\) be the Terwilliger algebras of \(\varGamma \) and \(\varDelta \) with respect to x, respectively. Assume, for an integer i with \(1 \le 2i \le D^Y\) and for \(y,z \in \varGamma _{2i}(x)\) with \(\partial _{\varGamma }(y,z)=2\), the numbers \(|\varGamma _{2i-1}(x) \cap \varGamma (y) \cap \varGamma (z)|\) and \(|\varGamma _{2i+1}(x) \cap \varGamma (y) \cap \varGamma (z)|\) depend only on i and do not depend on the choice of y, z. The first goal in this paper is to show the relations between T-modules of \(\varGamma \) and \(T'\)-modules of \(\varDelta \). Assume \(\varGamma \) is the incidence graph of the Hamming graph H(D, n) on the vertex set Y and the set \({\mathcal {C}}\) of all maximal cliques. Then, \(\varGamma \) satisfies above assumption and \(\varDelta \) is isomorphic to H(D, n). The second goal is to determine the irreducible T-modules of \(\varGamma \). For each irreducible T-module W, we give a basis for W the action of the adjacency matrix on this basis and we calculate the multiplicity of W.     

Anti-Ramsey Numbers of Graphs with Small Connected Components

The anti-Ramsey number, AR(n, G), for a graph G and an integer \(n\ge |V(G)|\), is defined to be the minimal integer r such that in any edge-colouring of \(K_n\) by at least r colours there is a multicoloured copy of G, namely, a copy of G that each of its edges has a distinct colour. In this paper we determine, for large enough \(n,\, AR(n,L\cup tP_2)\) and \(AR(n,L\cup kP_3)\) for any large enough t and k, and a graph L satisfying some conditions. Consequently, we determine AR(n, G), for large enough n, where G is \(P_3\cup tP_2\) for any \(t\ge 3,\, P_4\cup tP_2\) and \(C_3\cup tP_2\) for any \(t\ge 2,\, kP_3\) for any \(k\ge 3,\, tP_2\cup kP_3\) for any \(t\ge 1,\, k\ge 2\), and \(P_{t+1}\cup kP_3\) for any \(t\ge 3,\, k\ge 1\). Furthermore, we obtain upper and lower bounds for AR(n, G), for large enough n, where G is \(P_{k+1}\cup tP_2\) and \(C_k\cup tP_2\) for any \(k\ge 4,\, t\ge 1\).     

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.     

Polynomially linked additive functions—II

We continue the study of additive functions \(f_k:R\rightarrow F \;(1\le k\le n)\) linked by an equation of the form \(\sum _{k=1}^n p_k(x)f_k(q_k(x))=0\), where the \(p_k\) and \(q_k\) are polynomials, R is an integral domain of characteristic 0, and F is the fraction field of R. A method is presented for solving all such equations. We also consider the special case \(\sum _{k=1}^n x^{m_k}f_k(x^{j_k})=0\) in which the \(p_k\) and \(q_k\) are monomials. In this case we show that if there is no duplication, i.e. if \((m_k,j_k)\ne (m_p,j_p)\) for \(k\ne p\), then each \(f_k\) is the sum of a linear function and a derivation of order at most \(n-1\). Furthermore, if this functional equation is not homogeneous then the maximal orders of the derivations are reduced in a specified way.     

Generalized Bernstein Operators on the Classical Polynomial Spaces

We study generalizations of the classical Bernstein operators on the polynomial spaces \(\mathbb {P}_{n}[a,b]\), where instead of fixing \(\mathbf {1}\) and x, we reproduce exactly \(\mathbf {1}\) and a polynomial \(f_1\), strictly increasing on [a, b]. We prove that for sufficiently large n, there always exist generalized Bernstein operators fixing \(\mathbf {1}\) and \(f_1\). These operators are defined by non-decreasing sequences of nodes precisely when \(f_1^\prime > 0\) on (a, b), but even if \(f_1^\prime \) vanishes somewhere inside (a, b), they converge to the identity.     

Packing chromatic number versus chromatic and clique number

The packing chromatic number \(\chi _{\rho }(G)\) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into sets \(V_i\), \(i\in [k]\), where each \(V_i\) is an i-packing. In this paper, we investigate for a given triple (a, b, c) of positive integers whether there exists a graph G such that \(\omega (G) = a\), \(\chi (G) = b\), and \(\chi _{\rho }(G) = c\). If so, we say that (a, b, c) is realizable. It is proved that \(b=c\ge 3\) implies \(a=b\), and that triples \((2,k,k+1)\) and \((2,k,k+2)\) are not realizable as soon as \(k\ge 4\). Some of the obtained results are deduced from the bounds proved on the packing chromatic number of the Mycielskian. Moreover, a formula for the independence number of the Mycielskian is given. A lower bound on \(\chi _{\rho }(G)\) in terms of \(\Delta (G)\) and \(\alpha (G)\) is also proved.     

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.     

Sums of powers of primes

Let \(k>-1\). The sum of the kth powers of the primes less than x is asymptotic to \(\pi (x^{k+1})\). We show that the sum is less than \(\pi (x^{k+1})\) for arbitrarily large x, and the reverse inequality also holds for arbitrarily large x. When \(k>0\), there is a bias toward the first inequality, and we explain why this should be true and why the reverse bias holds when \(-1<k<0\).     

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.     

<Emphasis Type="Italic">b</Emphasis>-Generalized Skew Derivations on Lie Ideals

Let R be a non-commutative prime ring, Z(R) its center, Q its right Martindale quotient ring, C its extended centroid, \(F\ne 0\) an b-generalized skew derivation of R, L a non-central Lie ideal of R, \(0\ne a\in R\) and \(n\ge 1\) a fixed integer. In this paper, we prove the following two results:

1. 1.
   If R has characteristic different from 2 and 3 and \(a[F(x),x]^n=0\), for all \(x\in L\), then either there exists an element \(\lambda \in C\), such that \(F(x)=\lambda x\), for all \(x\in R\) or R satisfies \(s_4(x_1,\ldots ,x_4)\), the standard identity of degree 4, and there exist \(\lambda \in C\) and \(b\in Q\), such that \(F(x)=bx+xb+\lambda x\), for all \(x\in R\).
    
2. 2.
   If \(\mathrm{{char}}(R)=0\) or \(\mathrm{{char}}(R) > n\) and \(a[F(x),x]^n\in Z(R)\), for all \(x\in R\), then either there exists an element \(\lambda \in C\), such that \(F(x)=\lambda x\), for all \(x\in R\) or R satisfies \(s_4(x_1,\ldots ,x_4)\).
    

     

Maximum scattered linear sets and MRD-codes

The rank of a scattered \({\mathbb F}_q\)-linear set of \({{\mathrm{{PG}}}}(r-1,q^n)\), rn even, is at most rn / 2 as it was proved by Blokhuis and Lavrauw. Existence results and explicit constructions were given for infinitely many values of r, n, q (rn even) for scattered \({\mathbb F}_q\)-linear sets of rank rn / 2. In this paper, we prove that the bound rn / 2 is sharp also in the remaining open cases. Recently Sheekey proved that scattered \({\mathbb F}_q\)-linear sets of \({{\mathrm{{PG}}}}(1,q^n)\) of maximum rank n yield \({\mathbb F}_q\)-linear MRD-codes with dimension 2n and minimum distance \(n-1\). We generalize this result and show that scattered \({\mathbb F}_q\)-linear sets of \({{\mathrm{{PG}}}}(r-1,q^n)\) of maximum rank rn / 2 yield \({\mathbb F}_q\)-linear MRD-codes with dimension rn and minimum distance \(n-1\).     

Relative Difference Sets and Hadamard Matrices from Perfect Quaternionic Arrays

Let \(G=\mathbf{C}_{n_1}\times \cdots \times \mathbf{C}_{n_m}\) be an abelian group of order \(n=n_1\dots n_m\), where each \(\mathbf{C}_{n_t}\) is cyclic of order \(n_t\). We present a correspondence between the (4n, 2, 4n, 2n)-relative difference sets in \(G\times Q_8\) relative to the centre \(Z(Q_8)\) and the perfect arrays of size \(n_1\times \dots \times n_m\) over the quaternionic alphabet \(Q_8\cup qQ_8\), where \(q=(1+i+j+k)/2\). In view of this connection, for \(m=2\) we introduce new families of relative difference sets in \(G\times Q_8\), as well as new families of Williamson and Ito Hadamard matrices with G-invariant components.     

Complexities of normal bases constructed from Gauss periods

Let q be a power of a prime p, and let \(r=nk+1\) be a prime such that \(r\not \mid q\), where n and k are positive integers. Under a simple condition on q, r and k, a Gauss period of type (n, k) is a normal element of \({\mathbb {F}}_{q}^{n}\) over \({\mathbb {F}}_q\); the complexity of the resulting normal basis of \({\mathbb {F}}_{q}^{n}\) over \({\mathbb {F}}_q\) is denoted by C(n, k; p). Recent works determined C(n, k; p) for \(k\le 7\) and all qualified n and q. In this paper, we show that for any given \(k>0\), C(n, k; p) is given by an explicit formula except for finitely many primes \(r=nk+1\) and the exceptional primes are easily determined. Moreover, we describe an algorithm that allows one to compute C(n, k; p) for the exceptional primes \(r=nk+1\). Our numerical results cover C(n, k; p) for \(k\le 20\) and all qualified n and q.     

On determination of positive-definiteness for an anisotropic operator

We study the positive-definiteness of a family of \(L^2(\mathbb {R})\) integral operators with kernel \(K_{t, a} (x, y) = \pi ^{-1} (1 + (x - y)^2+ a(x^2 + y^2)^t)^{-1}\), for \(t > 0\) and \(a > 0\). For \(0 < t \le 1\) and \(a > 0\), the known theory of positive-definite kernels and conditionally negative-definite kernels confirms positive-definiteness. For \(t > 1\) and a sufficiently large, the integral operator is not positive-definite. For t not an integer, but with integer odd part, the integral operator is not positive-definite.