Intertwining wavelets or multiresolution analysis on graphs through random forests

We propose a new method for performing multiscale analysis of functions defined on the vertices of a finite connected weighted graph. Our approach relies on a random spanning forest to downsample the set of vertices, and on approximate solutions of Markov intertwining relation to provide a subgraph structure and a filter bank leading to a wavelet basis of the set of functions. Our construction involves two parameters q and $q^{\prime }$. The first one controls the mean number of kept vertices in the downsampling, while the second one is a tuning parameter between space localization and frequency localization. We provide an explicit reconstruction formula, bounds on the reconstruction operator norm and on the error in the intertwining relation, and a Jackson-like inequality. These bounds lead to recommend a way to choose the parameters q and $q^{\prime }$. We illustrate the method by numerical experiments.     

Fq-linear codes over Fq-algebras

Huffman (2013) [12] studied ${\mathbb{F}}_q$-linear codes over ${\mathbb{F}}_{q^m}$ and he proved the MacWilliams identity for these codes with respect to ordinary and Hermitian trace inner products. Let S be a finite commutative ${\mathbb{F}}_q$-algebra. An ${\mathbb{F}}_q$-linear code over S of length n is an ${\mathbb{F}}_q$-submodule of $S^n$. In this paper, we study ${\mathbb{F}}_q$-linear codes over S. We obtain some bounds on minimum distance of these codes, and some large classes of MDR codes are introduced. We generalize the ordinary and Hermitian trace products over ${\mathbb{F}}_q$-algebras and we prove the MacWilliams identity with respect to the generalized form. In particular, we obtain Huffman's results on the MacWilliams identity. Among other results, we give a theory to construct a class of quantum codes and the structure of ${\mathbb{F}}_q$-linear codes over finite commutative graded ${\mathbb{F}}_q$-algebras.     

The estimated number of irreducible binomials

Let ${\mathbb{F}}_q$ be the finite field with q elements, and T a positive integer. In this article, we find an asymptotic formula for the total number of monic irreducible binomials in ${\mathbb{F}}_q[x]$ of degree less or equal to T, when T is large enough. We also show explicit lower and upper bounds for the number of binomials in the case when T is small.     

New lower bounds on 2-spontaneous emission error designs

The combinatorial object named $t$-spontaneous emission error design ($t$-SEED) was proposed by Beth et al. in 2003 in order to correct errors caused by quantum jumps. The newly rising category of $t$-SEEDs has been studied extensively in recent years. Especially, the maximal possible dimensions for 2-SEEDs with block size 3 were determined completely; lower bounds on 2-SEEDs were established by applying affine groups. In this paper we utilize the action of twisted affine groups on finite fields and obtain new lower bounds on the dimensions of 2-$(q^2,k;m)$ SEEDs, some of which outperform the known ones.     

Highly nonlinear functions over finite fields

We consider a generalisation of a conjecture by Patterson and Wiedemann from 1983 on the Hamming distance of a function from ${\mathbb{F}}_q^n$ to ${\mathbb{F}}_q$ to the set of affine functions from ${\mathbb{F}}_q^n$ to ${\mathbb{F}}_q$. We prove the conjecture for each q such that the characteristic of ${\mathbb{F}}_q$ lies in a subset of the primes with density 1 and we prove the conjecture for all q by assuming the generalised Riemann hypothesis. Roughly speaking, we show the existence of functions for which the distance to the affine functions is maximised when n tends to infinity. This also determines the asymptotic behaviour of the covering radius of the $[q^n,n+1]$ Reed-Muller code over ${\mathbb{F}}_q$ and so answers a question raised by Leducq in 2013. Our results extend the case $q=2$, which was recently proved by the author and which corresponds to the original conjecture by Patterson and Wiedemann. Our proof combines evaluations of Gauss sums in the semiprimitive case, probabilistic arguments, and methods from discrepancy theory.     

Schatten properties,nuclearity and minimality of phase shift invariant spaces

We extend Feichtinger's minimality property on the smallest non-trivial time-frequency shift invariant Banach space, to the quasi-Banach case. Analogous properties are deduced for certain matrix spaces.We use these results to prove that the pseudo-differential operator $\mathrm{Op}(a)$ is a Schatten-q operator from $M^{\infty }$ to $M^p$ and r-nuclear operator from $M^{\infty }$ to $M^r$ when $a\in M^r$ for suitable p, q and r in $(0,\infty ]$.     

On actions of Drinfel'd doubles on finite dimensional algebras

Let q be an nth root of unity for $n>2$ and let $T_n(q)$ be the Taft (Hopf) algebra of dimension $n^2$. In 2001, Susan Montgomery and Hans-Jürgen Schneider classified all non-trivial $T_n(q)$-module algebra structures on an n-dimensional associative algebra A. They further showed that each such module structure extends uniquely to make A a module algebra over the Drinfel'd double of $T_n(q)$. We explore what it is about the Taft algebras that leads to this uniqueness, by examining actions of (the Drinfel'd double of) Hopf algebras H “close” to the Taft algebras on finite-dimensional algebras analogous to A above. Such Hopf algebras H include the Sweedler (Hopf) algebra of dimension 4, bosonizations of quantum linear spaces, and the Frobenius–Lusztig kernel $u_q({\mathfrak{sl}}_2)$.     

Tight wavelet frame sets in finite vector spaces

Let $q\ge 2$ be an integer, and ${\mathbb{F}}_q^d$, $d\ge 1$, be the vector space over the cyclic space ${\mathbb{F}}_q$. The purpose of this paper is two-fold. First, we obtain sufficient conditions on $E?{\mathbb{F}}_q^d$ such that the inverse Fourier transform of $1_E$ generates a tight wavelet frame in $L^2({\mathbb{F}}_q^d)$. We call these sets (tight) wavelet frame sets. The conditions are given in terms of multiplicative and translational tilings, which is analogous with Theorem 1.1 ([20]) by Wang in the setting of finite fields. In the second part of the paper, we exhibit a constructive method for obtaining tight wavelet frame sets in ${\mathbb{F}}_q^d$, $d\ge 2$, q an odd prime and $q\equiv 3$ (mod 4).     

On the existence of primitive completely normal bases of finite fields

Let ${\mathbb{F}}_q$ be the finite field of characteristic p with q elements and ${\mathbb{F}}_{q^n}$ its extension of degree n. We prove that there exists a primitive element of ${\mathbb{F}}_{q^n}$ that produces a completely normal basis of ${\mathbb{F}}_{q^n}$ over ${\mathbb{F}}_q$, provided that $n=p^{?}m$ with $(m,p)=1$ and $q>m$.