On the Complexity of Parallel Algorithms for Computing Inverses in GF(2^m) with m Prime

Inversion over a finite field is usually an expensive operation which is a crucial issue in many applications, such as cryptography and error-control codes. In this paper, three different strategies for computing the inverse over binary finite fields , called Eulerian, Gaussian, and Euclidean, respectively, are discussed and compared in terms of time and space complexity. In particular, some new upper and lower bounds to the respective complexities are evaluated.     

Infinitely many low- and high-energy solutions for a class of elliptic equations with variable exponent

This paper is concerned with the $p(x)$-Laplacian equation of the form $$ \left\{\begin{array}{ll} -\Delta_{p(x)} u=Q(x)|u|^{r(x)-2}u, &\mbox{in}\ \Omega,\u=0, &\mbox{on}\ \partial \Omega, \end{array}\right. \eqno{0.1} $$ where $\Omega\subset\R^N$ is a smooth bounded domain, $1p^+$ and $Q: \overline{\Omega}\to\R$ is a nonnegative continuous function. We prove that (0.1) has infinitely many small solutions and infinitely many large solutions by using the Clark''s theorem and the symmetric mountain pass lemma.     

Fast algorithms for determining the linear complexities of sequences over GF(p~m) with the period 3n

In this paper, for the the primes p such that 3 is a divisor of p-1, we prove a result which reduces the computation of the linear complexity of a sequence over GF(pm)(any positive integer m) with the period 3n (n and pm - 1 are coprime) to the computation of the linear complexities of three sequences with the period n. Combined with some known algorithms such as generalized Games-Chan algorithm, Berlekamp-Massey algorithm and Xiao-Wei-Lam-lmamura algorithm, we can determine the linear complexity of any sequence over GF(pm) with the period 3n (n and pm - 1 are coprime) more efficiently.     

On the linear complexity of binary threshold sequences derived from Fermat quotients

We determine the linear complexity of a family of p ²-periodic binary threshold sequences derived from Fermat quotients modulo an odd prime p, where p satisfies ${2^{p-1} \not\equiv 1 ({\rm mod}\, {p^2})}$ . The linear complexity equals p ² ? p or p ² ? 1, depending whether ${p \equiv 1}$ or 3 (mod 4). Our research extends the results from previous work on the linear complexity of the corresponding binary threshold sequences when 2 is a primitive root modulo p ². Moreover, we present a partial result on their linear complexities for primes p with ${2^{p-1} \equiv 1 ({\rm mod} \,{p^2})}$ . However such so called Wieferich primes are very rare.     

Reducing the calculation of the linear complexity of u2 v -periodic binary sequences to Games–Chan algorithm

We show that the linear complexity of a u2 ^v -periodic binary sequence, u odd, can easily be calculated from the linear complexities of certain 2 ^v -periodic binary sequences. Since the linear complexity of a 2 ^v -periodic binary sequence can efficiently be calculated with the Games-Chan algorithm, this leads to attractive procedures for the determination of the linear complexity of a u2 ^v -periodic binary sequence. Realizations are presented for u = 3, 5, 7, 15.      

$C_2 \oplus C_{2n}$上零和自由序列的结构

已知在任意有限循环群中, 一个零和自由序列的长度超过其Davenport常数的一半时, 该序列是光滑的. 本文给出了一类非循环阿贝尔群$C_2 \oplus C_{2n}$上 长度不小于$n+3$的零和自由序列的结构及性质.     

Boundedness of Commutators of θ-Type Calderόn-Zygmund Operators on Non-homogeneous Metric Measure Spaces

Let(X, d, μ) be a metric measure space satisfying both the upper doubling and the geometrically doubling conditions in the sense of Hyt?nen. In this paper, the authors obtain the boundedness of the commutators of θ-type Calderón-Zygmund operators with RBMO functions from L~∞(μ) into RBMO(μ) and from H_(at)~(1,∞)(μ) into L~1(μ), respectively.As a consequence of these results, they establish the L~p(μ) boundedness of the commutators on the non-homogeneous metric spaces.     

Remarks on the <Emphasis Type="Italic">k</Emphasis>-error linear complexity of <Emphasis Type="Italic">p</Emphasis><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>-periodic sequences

Recently the first author presented exact formulas for the number of 2 ⁿ -periodic binary sequences with given 1-error linear complexity, and an exact formula for the expected 1-error linear complexity and upper and lower bounds for the expected k-error linear complexity, k ≥ 2, of a random 2 ⁿ -periodic binary sequence. A crucial role for the analysis played the Chan–Games algorithm. We use a more sophisticated generalization of the Chan–Games algorithm by Ding et al. to obtain exact formulas for the counting function and the expected value for the 1-error linear complexity for p ⁿ -periodic sequences over prime. Additionally we discuss the calculation of lower and upper bounds on the k-error linear complexity of p ⁿ -periodic sequences over .      

On the Linear Complexity of the Sidelnikov-Lempel-Cohn-Eastman Sequences

In [6] and [10], a construction of binary sequences with an (almost) optimal autocorrelation spectrum is suggested. We continue the study of the linear complexity and the linear feedback polynomial of these sequences over $ \mathbb{F} $ ₂, originated in [4].     

Projektive Skalen,Tschebyscheff-Polynome und Fibonacci-Zahlen

Summary. Let $\widehat{\widehat T}_n$ and $\overline U_n$ denote the modified Chebyshev polynomials defined by $\widehat{\widehat T}_n (x) = {T_{2n + 1} \left(\sqrt{x + 3 \over 4} \right) \over \sqrt{x + 3 \over 4}}, \quad \overline U_{n}(x) = U_{n} \left({x + 1 \over 2}\right) \qquad (n \in \mathbb{N}_{0},\ x \in \mathbb{R}).$ For all $n \in \mathbb{N}_{0}$ define $\widehat{\widehat T}_{-(n + 1)} = \widehat{\widehat T}_n$ and $\overline U_{-(n + 2)} = - \overline U_n$, furthermore $\overline U_{-1} = 0$. In this paper, summation formulae for sums of type $\sum\limits^{+\infty}_{k = -\infty} \mathbf a_{\mathbf k}(\nu; x)$ are given, where $\bigl(\mathbf a_{\mathbf k}(\nu; x)\bigr)^{-1} = (-1)^k \cdot \Bigl( x \cdot \widehat{\widehat T}_{\left[k + 1 \over 2\right] - 1} (\nu) +\widehat{\widehat T}_{\left[k + 1 \over 2\right]}(\nu)\Bigr) \cdot \Bigl(x \cdot \overline U_{\left[k \over 2\right] - 1} (\nu) + \overline U_{\left[k \over 2\right]} (\nu)\Bigr)$ with real constants $ x, \nu $. The above sums will turn out to be telescope sums. They appear in connection with projective geometry. The directed euclidean measures of the line segments of a projective scale form a sequence of type $(\mathbf a_{\mathbf k} (\nu;x))_{k \in \mathbb{Z}}$ where $ \nu $ is the cross-ratio of the scale, and x is the ratio of two consecutive line segments once chosen. In case of hyperbolic $(\nu \in \mathbb{R} \setminus] - 3,1[)$ and parabolic $\nu = -3$ scales, the formula $\sum\limits^{+\infty}_{k = -\infty} \mathbf a_{\mathbf k} (\nu; x) = {\frac{1}{x - q_{{+}\atop(-)}}} - {\frac{1}{x - q_{{-}\atop(+)}}} \eqno (1)$ holds for $\nu > 1$ (resp. $\nu \leq - 3$), unless the scale is geometric, that is unless $x = q_+$ or $x = q_-$. By $q_{\pm} = {-(\nu + 1) \pm \sqrt{(\nu - 1)(\nu + 3)} \over 2}$ we denote the quotient of the associated geometric sequence.

     

Painlev\''{e} Analysis and Auto-B\"{a}cklund Transformation for a General Variable Coefficient Burgers Equation with Linear Damping Term

This paper investigates a general variable coefficient (gVC) Burgers equation with linear damping term. We derive the Painlev\''{e} property of the equation under certain constraint condition of the coefficients. Then we obtain an auto-B\"{a}cklund transformation of this equation in terms of the Painlev\''{e} property. Finally, we find a large number of new explicit exact solutions of the equation. Especially, infinite explicit exact singular wave solutions are obtained for the first time. It is worth noting that these singular wave solutions will blow up on some lines or curves in the $(x,t)$ plane. These facts reflect the complexity of the structure of the solution of the gVC Burgers equation with linear damping term. It also reflects the complexity of nonlinear wave propagation in fluid from one aspect.     

On Matroids Representable over and other Fields

The matroids that are representable over and some other fields depend on the choice of field. This paper gives matrix characterisations of the classes that arise. These characterisations are analogues of the characterisation of regular matroids as the ones that can be represented over the rationals by a totally-unimodular matrix. Some consequences of the theory are as follows. A matroid is representable over and if and only if it is representable over and the rationals, and this holds if and only if it is representable over for all odd primes . A matroid is representable over and the complex numbers if and only if it is representable over and . A matroid is representable over , and if and only if it is representable over every field except possibly . If a matroid is representable over for all odd primes , then it is representable over the rationals.

     

R\''enyi公式的推广

在本文,作为著名的R\''enyi公式(其刻画了标号连通单圈图的计数显式)的自然推广,我们研究了标号匀称$(k+1)$秩$(p,~q)$超单圈的计数问题,给出了如下的计数显式:$$U_{p,~q}^{(k+1)}=\begin{cases} \frac{p!}{2[(k-1)!]^q}\cdot\sum_{t=2}^q \frac{q^{q-t-1}\cdot sgn(tk-2)}{(q-t)!}, & p=qk, \\ 0,& p\neq qk, \end{cases}$$其中$k,~p,~q$均为正整数.     

On the numerical computation of blowing‐up solutions for semilinear parabolic equations

Theoretical aspects related to the approximation of the semilinear parabolic equation: $u_t=\Delta u+f(u)$\nopagenumbers\end , with a finite unknown ‘blow‐up’ time T_b have been studied in a previous work. Specifically, for ε a small positive number, we have considered coupled systems of semilinear parabolic equations, with positive solutions and ‘mass control’ property, such that: \def\ve{^\varepsilon}$$u_t\ve=\Delta u\ve+f(u\ve)v\ve\qquad v_t\ve=\Delta v\ve‐\varepsilon f(u\ve)v\ve$$\nopagenumbers\end The solution \def\ve{^\varepsilon}$$\{u\ve,v\ve\}$$\nopagenumbers\end of such systems is known to be global. It is shown that $$\|(u^\varepsilon‐u)(\, .\, ,t)\|_\infty\leq C(M_T)\varepsilon$$\nopagenumbers\end , \def\lt{\char'74}$t\leq T \lt T_b$\nopagenumbers\end where $M_T=\|u(\, .\, ,T)\|_\infty$\nopagenumbers\end and $C(M_T)$\nopagenumbers\end is given by (6). In this paper, we suggest a numerical procedure for approaching the value of the blow‐up time T_b and the blow‐up solution u. For this purpose, we construct a sequence $\{M_\eta\}$\nopagenumbers\end , with $\lim_{\eta\rightarrow 0}M_\eta=\infty$\nopagenumbers\end . Correspondingly, for $\varepsilon\leq1/2C(M_\eta+1)=\eta^\alpha$\nopagenumbers\end and \def\lt{\char'74}$0\lt\alpha\lt\,\!1$\nopagenumbers\end , we associate a specific sequence of times $\{T_\varepsilon\}$\nopagenumbers\end , defined by $\|u^\varepsilon(\, .\, ,T_\varepsilon)\|_\infty=M_\eta$\nopagenumbers\end . In particular, when $\varepsilon=\eta\leq\eta^\alpha$\nopagenumbers\end , the resulting sequence $\{T_\varepsilon\equiv T_\eta\}$\nopagenumbers\end , verifies, $\|(u‐u^\eta)(\, .\, ,t)\|_\infty\leq{1\over2}(\eta)^{1‐\alpha}$\nopagenumbers\end , \def\lt{\char'74}$0\leq t\leq T_\eta\lt T_{\rm b}$\nopagenumbers\end with $\lim_{\eta\rightarrow 0}T_\eta=T_{\rm b}$\nopagenumbers\end . The two special cases of a single‐point blow‐up where $f(u)=\lambda{\rm e}^u$\nopagenumbers\end and $f(u)=u^p$\nopagenumbers\end are then studied, yielding respectively sequences $\{M_\eta\}$\nopagenumbers\end of order $O(\ln|\ln(\eta)|)$\nopagenumbers\end and $O(\{|\ln(\eta)|\}^{1/p‐1})$\nopagenumbers\end . The estimate $|T_\eta‐T_{\rm b}|/T_{\rm b}=O(1/|\ln(\eta)|)$\nopagenumbers\end is proven to be valid in both cases. We conduct numerical simulations that confirm our theoretical results. Copyright © 2001 John Wiley & Sons, Ltd.     

有限偏差映射的加权Grotzsch问题

考虑如下的极值问题: $$ \inf_{f\in \mathcal{F}}\iint_{Q_{1}}\varphi(K(z,f))\lambda(x)|\rmd z|^{2}, $$ 其中$\mathcal{F}$ 是从矩形$Q_1$ 到矩形$Q_2$ 并保持端点且具有有限线性偏差 $K(z,f)$的所有同胚映射$f$的集合, $\varphi$ 是正的严格凸的递增函数, 而$\lambda(x)$ 是正的加权函数. 作者在文``{\it Sci China Math}, 2016, 59(4):673--686''中证明了当 $\varphi''$ 无界时, 上述极值问题存在唯一的极值映射$f_{0}(z)=u(x)+\rmi y$. 本文考虑$\varphi''$ 有界的情形, 得到如下结果: 当$Ll$ 时, 极值映射可能不存在. 借助于 Martin 和 Jordens 的方法, 构造了一族最小序列使得其极限达到最小值.     

Poincar{\''e} Bifurcation from an Elliptic Hamiltonian of Degree Four with Two-saddle Cycle

In this paper, we consider Poincar{\''e} bifurcation from an elliptic Hamiltonian of degree four with two-saddle cycle. Based on the Chebyshev criterion, not only one case in the Li{\''e}nard equations of type $(3, 2)$ is discussed again in a different way from the previous ones, but also its two extended cases are investigated, where the perturbations are given respectively by adding $\varepsilon y(d_0 + d_2 v^{2n})\frac{\partial }{{\partial y}}$ with $ n\in \mathbb{N^+}$ and $\varepsilon y(d_0 + d_4 {v^4}+ d_2 v^{2n+4})\frac{\partial }{{\partial y}}$ with $n=-1$ or $ n\in \mathbb{N^+}$, for small $\varepsilon > 0$. For the above cases, we obtain all the sharp upper bound of the number of zeros for Abelian integrals, from which the existence of limit cycles at most via the first-order Melnikov functions is determined. Finally, one example of double limit cycles for the latter case is given.     

Inverse problems in magneto-electroscanning (in encephalography, for magnetic microscopes, etc.)

Contrary to the prevailing opinion about the incorrectness of the inverse MEEG-problem, we prove its unique solvability in the framework of the system of Maxwell''s equations [3]. The solution of this problem is the distribution of ${\bf y} \mapsto {\bf q}({\bf y})$ current dipoles of brain neurons that occupies the region $Y \subset \mathbb{R}^3 $. It is uniquely determined by the non-invasive measurements of the electric and magnetic fields induced by the current dipoles of neurons on the patient"s head. The solution can be represented in the form ${\bf q}={\bf q}_0+{\bf p}_0\delta\Big|_{\partial Y}$, where ${\bf q}_0$ is the usual function defined in $Y,$ and ${\bf p}_0\delta\Big|_{\partial Y} $ is a $\delta$-function on the boundary of the domain $Y$ with a certain density ${\bf p}_0$. It is essential that ${\bf p}_0$ and ${\bf q}_0$ are interrelated. This ensures the correctness of the inverse MEEG-problem. However, the components of the required 3-dimensional distribution $ {\bf q} $ must turn out to be linearly dependent if only the magnetic field ${\bf B}$ is taken into account. This question is considered in detail in a flat model of the situation.     

Double Biproduct Hom-Bialgebra and Related Quasitriangular Structures

Let(H, β) be a Hom-bialgebra such that β~2= id_H.(A, α_A) is a Hom-bialgebra in the left-left Hom-Yetter-Drinfeld category (_H~H)YD and(B, α_B) is a Hom-bialgebra in the right-right Hom-Yetter-Drinfeld category YD_H~H. The authors define the two-sided smash product Hom-algebra(A■H■B, α_A ? β ? α_B) and the two-sided smash coproduct Homcoalgebra(A◇H◇B, α_A ? β ? α_B). Then the necessary and sufficient conditions for(A■H■B, α_A ? β ? α_B) and(A◇H◇B, α_A ? β ? α_B) to be a Hom-bialgebra(called the double biproduct Hom-bialgebra and denoted by(A_◇~■H_◇~■B, α_A ? β ? α_B)) are derived. On the other hand, the necessary and sufficient conditions for the smash coproduct Hom-Hopf algebra(A◇H, α_A ? β) to be quasitriangular are given.     

因子谱与诱导序列

对于任意给定的性质${\mathcal{P}}$和序列$\rho$, 词上的组合领域一个重要的研究课题是找出所有的因子$\omega$和序数$p$,使得序列$\rho$中第$p$次出现的因子$\omega$ (记为$\omega_p$) 满足性质${\mathcal{P}}$.这个问题等价于研究``因子谱''.确定因子谱是一个困难的问题. 为了实现目标,我们引入并研究了一系列的概念:核词、包络词、回归词和任意因子的诱导序列. 利用因子谱和诱导序列,我们可以解决序列中的一些计数问题.例如:在序列的任意一个片段中回文或者高次方词的个数. 本文中,我们将结合几个特殊的序列展示相关的研究结果.这些序列包括: Fibonacci序列、Tribonacci序列、Period-doubling序列等等. 我们相信这些概念和方法对于所有的一致常返序列都是有效的.     

Characterization of 2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>-periodic binary sequences with fixed 2-error or 3-error linear complexity

The linear complexity of sequences is an important measure of the cryptographic strength of key streams used in stream ciphers. The instability of linear complexity caused by changing a few symbols of sequences can be measured using k-error linear complexity. In their SETA 2006 paper, Fu et al. (SETA, pp. 88–103, 2006) studied the linear complexity and the 1-error linear complexity of 2 ⁿ -periodic binary sequences to characterize such sequences with fixed 1-error linear complexity. In this paper we study the linear complexity and the k-error linear complexity of 2 ⁿ -periodic binary sequences in a more general setting using a combination of algebraic, combinatorial, and algorithmic methods. This approach allows us to characterize 2 ⁿ -periodic binary sequences with fixed 2- or 3-error linear complexity. Using this characterization we obtain the counting function for the number of 2 ⁿ -periodic binary sequences with fixed k-error linear complexity for k = 2 and 3.