\documentclass[12pt]{article} \usepackage{e-jc} \specs{P2.12}{22(2)}{2015} \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \begin{document} \theoremstyle{plain} \newtheorem{thm}{Theorem} \newtheorem{lm}[thm]{Lemma} \newtheorem{cor}[thm]{Corollary} \newtheorem{prop}[thm]{Proposition} %\newtheorem{con}[thm]{Conjecture} \newtheorem{cla}[thm]{Claim} \theoremstyle{definition} \newtheorem{dfn}[thm]{Definition} \newtheorem{example}[thm]{Example} \newtheorem{alg}[thm]{Algorithm} \newtheorem{prob}[thm]{Problem} \theoremstyle{remark} \newtheorem{rem}[thm]{Remark} \newcommand{\A}{\mathcal{A}} \newcommand{\B}{\mathcal{B}} \newcommand{\D}{\mathcal{D}} \newcommand{\E}{\mathcal{E}} \newcommand{\F}{\mathcal{F}} \title{\bf A generalization of very odd sequences} \author{ Cheng Yeaw Ku \\ \small Department of Mathematics \\[-0.8ex] \small National University of Singapore \\[-0.8ex] \small Singapore 117543.\\ \small\tt matkcy@nus.edu.sg\\ \and Kok Bin Wong\\ \small Institute of Mathematical Sciences \\[-0.8ex] \small University of Malaya \\[-0.8ex] \small 50603 Kuala Lumpur, Malaysia\\ \small\tt kbwong@um.edu.my } \date{\dateline{Mar 2, 2015}{Apr 6, 2015}{Apr 21, 2015}\\ \small Mathematics Subject Classifications: 11B50, 11B83 } \maketitle \begin{abstract}\noindent Let $\mathbb N$ be the set of positive integers and $n\in \mathbb N$. Let $\mathbf{a}=(a_0,a_1,\dots, a_{n-1})$ be a sequence of length $n$, with $a_i\in \{0,1\}$. For $0\leq k\leq n-1$, let \begin{equation} A_k(\mathbf{a})=\sum_{\substack{0\leq i\leq j\leq n-1\\ j-i=k}} a_ia_j.\notag \end{equation} The sequence $\mathbf{a}$ is called a very odd sequence if $A_k(\mathbf{a})$ is odd for all $0\leq k\leq n-1$. In this paper, we study a generalization of very odd sequences and give a characterisation of these sequences. \end{abstract} \bigskip\noindent \textbf{Keywords:} very odd sequence, Pelik\'an's conjecture\\ \section{Introduction} Let $\mathbb N$ be the set of positive integers and $n\in \mathbb N$. Let $\mathbf{a}=(a_0,a_1,\dots, a_{n-1})$ be a sequence of length $n$, with $a_i\in \{0,1\}$. For $0\leq k\leq n-1$, let \begin{equation} A_k(\mathbf{a})=\sum_{\substack{0\leq i\leq j\leq n-1\\ j-i=k}} a_ia_j.\notag \end{equation} The sequence $\mathbf{a}$ is called a \emph{very odd sequence} if $A_k(\mathbf{a})$ is odd for all $0\leq k\leq n-1$. Pelik\'an \cite{Pelikan} conjectured that very odd sequences of length $n\geq 5$ do not exist. Later, Alles \cite{Alles} and MacWilliams and Odlyzko \cite{William} proved that Pelik\'an conjecture is false (see also \cite{Moree}). In fact, Inglis and Wiseman \cite{Inglis} and MacWilliams and Odlyzko \cite{William} proved the following theorem which gives a necessary and sufficient condition for the existence of a very odd sequences of length $n$. \begin{thm}\label{thm_basic} A very odd sequence of length $n> 1$ exists if and only if the order of $2$ is odd in the multiplicative group of integers modulo $2n - 1$. \end{thm} Let $p$ be a prime and $\mathbf{z}=(z_0,z_1,z_2,\dots )$ be an infinite sequence. A sequence $\mathbf{a}=(a_0,a_1,\dots, a_{n-1})$ of length $n$ with $a_i\in\mathbb N\cup \{0\}$ is called a $(\mathbf{z},p)$-\emph {sequence} if \begin{align*} A_k(\mathbf{a})\equiv z_k\mod p,\ \ \forall\ \ 0\leq k\leq n-1. \end{align*} For each $k\in\mathbb N\cup \{0\}$, let $\overline k=(k,k,k,\dots )$ be the infinite sequence with all entries equal to $k$. Then, Theorem \ref{thm_basic} can be rewritten as follows: \begin{thm}\label{thm_basic_new} A $(\overline 1,2)$-sequence of length $n> 1$ exists if and only if the order of $2$ is odd in the multiplicative group of integers modulo $2n - 1$. \end{thm} In this paper, we give necessary and sufficient conditions for the existence of a $(\overline k,p)$-sequence of length $n> 1$ (Theorem \ref{thm_main}). We will also consider the existence of a $(\mathbf y_k,p)$-sequence of length $n> 1$ (Theorem \ref{thm_main2}) where $\mathbf y_k=(y_0,y_1,y_2,\dots )$ and $y_i=(-1)^ik$. \section{Main Results} Let $p$ be a prime and $\mathbb Z_p$ be the field with $p$ elements. We shall denote the set of all polynomials over the field $\mathbb Z_p$ by $\mathbb Z_p[x]$. For any sequence $\mathbf{a}=(a_0,a_1,\dots, a_{n-1})$ of length $n$ with $a_i\in\mathbb N\cup \{0\}$, we set \begin{align*} f_{\mathbf a} (x)= a_0+a_1x+\cdots +a_{n-1}x^{n-1}. \end{align*} Then $f_{\mathbf a} (x)\in \mathbb Z_p[x]$. For a polynomial $g(x)=c_0+c_1x+\cdots +c_{n-1}x^{n-1}\in \mathbb Z_p[x]$, we set \begin{align*} g^* (x)= c_{n-1}+c_{n-2}x+\cdots +c_0x^{n-1}. \end{align*} Note that $g^*(x)=x^{n-1}g\left(\frac{1}{x}\right)$ and $\left(g^*(x)\right)^*=g(x)$. Furthermore, $f_{\mathbf a}^* (x)=f_{\mathbf a^*} (x)$ where $\mathbf a^*=(a_{n-1},\dots, a_1,a_0)$ is the reverse of $\mathbf{a}=(a_0,a_1,\dots, a_{n-1})$. The following two lemmas are obvious. \begin{lm}\label{lm_factor} Let $f(x),g(x),h(x)$ be polynomials of degree at least 1 in $\mathbb Z_p[x]$. If $f(x)=g(x)h(x)$, then $f^*(x)=g^*(x)h^*(x)$. \end{lm} \begin{lm}\label{lm_irreducible} If $f(x)$ is a monic irreducible polynomial in $\mathbb Z_p[x]$, then $\frac{1}{f(0)}f^*(x)$ is also a monic irreducible polynomial in $\mathbb Z_p[x]$. \end{lm} \begin{lm}\label{lm_elementary_relation} A sequence $\mathbf{a}=(a_0,a_1,\dots, a_{n-1})$ is a $(\mathbf{z},p)$-{sequence} if and only if \begin{align*} f_{\mathbf a} (x)f_{\mathbf a}^* (x)=\sum_{i=0}^{n-1} z_{n-1-i}x^i +x^{n-1}\sum_{i=1}^{n-1} z_ix^{i}, \end{align*} in $\mathbb Z_p[x]$. \end{lm} \begin{proof} Note that \begin{align*} f_{\mathbf a} (x)f_{\mathbf a}^* (x) & =\left(\sum_{i=0}^{n-1} a_ix^i\right)\left(\sum_{j=0}^{n-1} a_jx^{n-1-j}\right)\\ & =\sum_{l=0}^{2n-2} \left(\sum_{\substack{0\leq i,j\leq n-1 \\ j-i=n-1-l}} a_ia_j\right) x^l\\ & =\sum_{l=0}^{2n-2} A_{\vert n-1-l \vert}(\mathbf{a})x^l\\ &=\sum_{i=0}^{n-1} A_{n-1-i}(\mathbf{a})x^i +x^{n-1}\sum_{i=1}^{n-1} A_i(\mathbf{a})x^{i}. \end{align*} The lemma follows by noting that $\mathbf{a}=(a_0,a_1,\dots, a_{n-1})$ is a $(\mathbf{z},p)$-{sequence} if and only if $A_i(\mathbf{a})\equiv z_i \mod p$ for all $i$. \end{proof} The following corollary follows immediately from Lemma \ref{lm_elementary_relation}. \begin{cor}\label{case_k_0} If $k\equiv 0\mod p$, then there is exactly one $(\overline k,p)$-sequence of length $n> 1$, which is $(\overbrace{0,0,\dots, 0}^n)$. \end{cor} We shall require the following lemmas. \begin{lm}\label{lm_division}\textnormal{(\cite[Theorem 2.14 on p. 128]{Jacobson})} Let $f(x)$ and $g(x)\neq 0$ be polynomials in $F[x]$, where $F$ is a field. Then there exist polynomials $q(x)$ and $r(x)\in F[x]$ with the degree of $r(x)$ less than the degree of $g(x)$ such that $f(x)=q(x)g(x)+r(x)$. \end{lm} \begin{lm}\label{lm_extension}\textnormal{(\cite[Theorem 4.26 on p. 288]{Jacobson})} Let $F$ be a finite field with $q=p^m$ elements and $E$ be a field extension of $F$ with $[E:F]=n$. Then the Galois group $G(E/F)$ is a cyclic group with generator $\eta$, where $\eta :a\rightarrow a^q$. \end{lm} Note that the Galois group $G(E/F)$ is the group of all automorphisms of $E$ that fix $F$, i.e., $\theta\in G(E/F)$ if and only if $\theta (a)=a$ for all $a\in F$ and $\theta\in\textnormal{Aut}(E)$ the group of all automorphisms of $E$. \begin{lm}\label{lm_multiple} \textnormal{(\cite[Section 4.4 on p. 229]{Jacobson})} Let $f(x)\in\mathbb Z_p[x]$ and $f'(x)$ be the formal derivative of $f(x)$. If $\beta$ is a multiple root of $f(x)$, then $f'(\beta)=0$. \end{lm} We denote the greatest common divisor of $c,d$ by $\gcd(c,d)$. \begin{lm}\label{lm_monic} Let $\gcd(p,2n-1)=1=\gcd(p-1,2n-1)$ and $\beta$ be a root of $\sum_{i=0}^{2n-2} x^i$. If $h(x)\in\mathbb Z_p[x]$ is a monic irreducible polynomial with $h(\beta)=0$ and the order of $p$ modulo $2n-1$ is odd, then the degree of $h(x)$ is odd and $h(0)=-1$. Furthermore, $-h^*(x)\neq h(x)$. \end{lm} \begin{proof} Let $E$ be a field extension of $\mathbb Z_p$ containing $\beta$. Let the order of $\beta$ in $E$ be $t$, i.e., $t$ is the least positive integer such that $\beta^t=1$. Note that $(x-1)\sum_{i=0}^{2n-2} x^i=x^{2n-1}-1$. So, $\beta$ is a root of $x^{2n-1}-1$, i.e., $\beta^{2n-1}=1$. This implies that $t$ divides $2n-1$ and $\gcd(p,t)=1=\gcd(p-1,t)$. Let the order of $p$ modulo $t$ be $e$. Then $\beta^{p^e}=\beta$ and $\beta^{p^i}\neq \beta$ for $1\leq i\leq e-1$. Furthermore, $e$ is odd as the order of $p$ modulo $2n-1$ is odd. By Lemma \ref{lm_extension}, the Galois group $G(E/\mathbb Z_p)$ is a cyclic group with generator $\eta$. Note that $\eta((x-\beta)(x-\beta^p)\dots (x-\beta^{p^{e-1}}))=(x-\beta)(x-\beta^p)\dots (x-\beta^{p^{e-1}})$. So, $(x-\beta)(x-\beta^p)\dots (x-\beta^{p^{e-1}})\in\mathbb Z_p[x]$ and $h(x)=(x-\beta)(x-\beta^p)\dots (x-\beta^{p^{e-1}})$. Thus, the degree of $h(x)$ is $e$ which is odd. Now, $(p-1)(1+p+\cdots +p^{e-1})=p^e-1\equiv 0\mod t$. Since $\gcd(p-1,t)=1$, we have $1+p+\cdots +p^{e-1}\equiv 0 \mod t$. Therefore $h(0)=(-1)^e\beta^{1+p+\cdots+p^{e-1}}=(-1)^e=-1$. By Lemma \ref{lm_irreducible}, $-h^*(x)$ is a monic irreducible polynomial and $-h^*(\beta^{-1})=0$. Suppose $-h^*(x)= h(x)$. Then $\beta^{p^{i_0}}=\beta^{-1}$ for some $0\leq i_0\leq e-1$. This implies that $p^{i_0}\equiv -1\mod t$ and $p^{2i_0}\equiv 1\mod t$. So, $e$ divides $2i_0$, and $e$ divides $i_0$ for $e$ is odd. This means that $p^{i_0}\equiv 1\mod t$ and $2\equiv 0\mod t$. Therefore, $t=1$ or $2$. If $t=1$, then $\beta=1$ and $0=\sum_{i=0}^{2n-2} \beta^i=2n-1$ (in $\mathbb Z_p$), contradicting the fact that $\gcd(p,2n-1)=1$. If $t=2$, then $2$ divides $2n-1$, which is another contradiction. Hence, $-h^*(x)\neq h(x)$. \end{proof} \begin{lm}\label{lm_factor2} Let $F$ be a field. Then $x^{m_1}-1=(x^{m_2}-1)w(x)$ for some polynomial $w(x)\in F[x]$ if and only if $m_2$ divides $m_1$. \end{lm} \begin{proof} Let $m_1=qm_2+r$ where $r,q$ are integers with $0\leq r 1$ exists if and only if \begin{itemize} \item[\textnormal{(a)}] the order of $p$ is odd in $U_{2n-1}$, \item[\textnormal{(b)}] $(-1)^{n-1}k$ is a quadratic residue modulo $p$. \end{itemize} Furthermore, if such a sequence exists, then there are exactly $2^l$ of them if $p=2$ and $2^{l+1}$ if $p$ is odd, where $2l$ is the number of irreducible factors of $\sum_{i=0}^{2n-2} x^i$. \end{thm} \begin{proof} ($\Rightarrow$) Let $\mathbf a=(a_0,a_1,\dots, a_{n-1})$ be a $(\overline k,p)$-sequence of length $n> 1$. By Lemma \ref{lm_elementary_relation}, \begin{align*} f_{\mathbf a} (x)f_{\mathbf a}^* (x)=k\sum_{i=0}^{2n-2} x^i. \end{align*} Note that $h(x)=(x-1)\sum_{i=0}^{2n-2} x^i=x^{2n-1}-1$ and $h'(x)=(2n-1)x^{n-2}\neq 0$ in $\mathbb Z_p[x]$ for $\gcd(p,2n-1)=1$. It follows from Lemma \ref{lm_multiple} that $h(x)$ has no multiple roots. Thus, $\sum_{i=0}^{2n-2} x^i$ has no multiple roots. Note that $a_{n-1}a_0=k\not\equiv 0\mod p$ for $a_{n-1}a_0$ is the coefficient of $x^{2n-2}$ in $f_{\mathbf a} (x)f_{\mathbf a}^* (x)$. So, $a_{n-1}\not\equiv 0\mod p$. Let $f_{\mathbf a} (x)=a_{n-1} q_1(x)q_2(x)\dots q_m(x)$ where each $q_i(x)$ is a monic irreducible polynomial. Suppose $p$ is of even order in $U_{2n-1}$. Let $2l$ be the order of $p$ modulo $2n-1$. Then $(p^l-1)(p^l+1)=p^{2l}-1\equiv 0\mod (2n-1)$. Let $\beta_1,\beta_2,\dots, \beta_{2n-2}$ be all the distinct roots of $\sum_{i=0}^{2n-2} x^i$. Then each $\beta_i$ is also a root of $x^{2n-1}-1$. Suppose $\beta_i^{p^l-1}=1$ for all $1\leq i\leq 2n-2$. Then each $\beta_i$ is a root of $x^{p^l-1}-1$. This implies that $x^{p^l-1}-1=(x^{2n-1}-1)w(x)$ for some $w(x)\in \mathbb Z_p[x]$. By Lemma \ref{lm_factor2}, $p^l\equiv 1 \mod (2n-1)$, a contradiction. So, $\beta_{i_0}^{p^l-1}\neq 1$ for some $1\leq i_0\leq 2n-2$. Let $\beta_{i_0}^{p^l-1}$ be a root of $q_{j_0}(x)$. Let $E$ be a field extension of $\mathbb Z_p$ containing $\beta_{i_0}^{p^l-1}$. By Lemma \ref{lm_extension}, the Galois group $G(E/\mathbb Z_p)$ is a cyclic group with generator $\eta$. Note that $\eta^{l}(\beta_{i_0}^{p^l-1})=\beta_{i_0}^{(p^l-1)p^l}=\beta_{i_0}^{(p^{2l}-1)+1-p^l}=\beta_{i_0}^{-(p^l-1)}$ where the last equality follows from $\beta_{i_0}^{2n-1}=1$ and $p^{2l}-1\equiv 0\mod 2n-1$. So, $\beta_{i_0}^{-(p^l-1)}$ is a root of $q_{j_0}(x)$. On the other hand, $\beta_{i_0}^{-(p^l-1)}$ is also a root of the monic irreducible polynomial $\frac{q_{j_0}^*(x)}{q_{j_0}(0)}$ (Lemma \ref{lm_irreducible}). This means $q_{j_0}(x)=\frac{q_{j_0}^*(x)}{q_{j_0}(0)}$. By Lemma \ref{lm_factor}, $\frac{q_{j_0}^*(x)}{q_{j_0}(0)}$ is an irreducible factor of $f_{\mathbf a}^* (x)$. Therefore, $\beta_{i_0}^{-(p^l-1)}$ a root of $\sum_{i=0}^{2n-2} x^i$ of multiplicity at least $2$, a contradiction. Hence, the order of $p$ is odd in $U_{2n-1}$. This proves part (a) of the theorem. By part (a) of the theorem and Lemma \ref{lm_monic}, the degree of $q_i(x)$ is odd and $q_i(0)=-1$ for $1\leq i\leq m$. Then by Lemma \ref{lm_factor}, \begin{align*} f_{\mathbf a}^* (x)& =a_{n-1}q_1(0)q_2(0)\dots q_m(0) \left(\frac{q_1^*(x)}{q_1(0)}\right)\left(\frac{q_2^*(x)}{q_2(0)}\right)\dots \left(\frac{q_m^*(x)}{q_m(0)}\right)\\ & =a_{n-1}(-1)^m \left(-q_1^*(x)\right)\left(-q_2^*(x)\right)\dots \left(-q_m^*(x)\right), \end{align*} where each $-q_i^*(x)$ is a monic irreducible polynomial (Lemma \ref{lm_irreducible}). Therefore $(-1)^mk \equiv a_{n-1}^2\mod p$. Let $e_i$ be the degree of $q_i(x)$. The degree of $f_{\mathbf a} (x)f_{\mathbf a}^* (x)$ is $2\sum_{i=1}^{m} e_i$. So, $2\sum_{i=1}^{m} e_i=2n-2$, i.e., $\sum_{i=1}^{m} e_i=n-1$. Since each $e_i$ is odd, we have $m\equiv \sum_{i=1}^{m} e_i\equiv n-1\mod 2$. Hence, $(-1)^m=(-1)^{n-1}$ and part (b) of the theorem follows. \vskip 0.5cm \noindent ($\Leftarrow$) Suppose (a) and (b) hold. Note that $\left(\sum_{i=0}^{2n-2} x^i\right)^*=\sum_{i=0}^{2n-2} x^i$. So, if $\beta$ is a root of $\sum_{i=0}^{2n-2} x^i$, then $\beta^{-1}$ is also a root of $\sum_{i=0}^{2n-2} x^i$. This means that if $h(x)$ is a monic irreducible polynomial appearing in the factorization of $\sum_{i=0}^{2n-2} x^i$, then by Lemma \ref{lm_irreducible} and \ref{lm_monic}, $-h^*(x)$ is also a monic irreducible polynomial appearing in the factorization of $\sum_{i=0}^{2n-2} x^i$. Furthermore, the degree of $h(x)$ and $-h^*(x)$ are odd and $-h^*(x)\neq h(x)$. So, we may write \begin{align*} \sum_{i=0}^{2n-2} x^i=h_1(x)h_2(x)\dots h_l(x)(-h_1^*(x))(-h_2^*(x))\dots (-h_l^*(x)). \end{align*} If $f_i$ is the degree of $h_i$, then $l\equiv \sum_{i=1}^l f_i\equiv n-1\mod 2$. Therefore $(-1)^l=(-1)^{n-1}$. Since $(-1)^{n-1}k$ is a quadratic residue modulo $p$, there exists an $a_{n-1}\in\mathbb Z_p\setminus \{0\}$ with $a_{n-1}^2\equiv (-1)^{n-1}k$. Now, there exists a unique $\mathbf b=(b_0,b_1,\dots ,b_{n-2},1)$ with $f_{\mathbf b} (x)=h_1(x)h_2(x)\dots h_l(x)$. Let $\mathbf a=a_{n-1}\mathbf b=(a_{n-1}b_0,a_{n-1}b_1,\dots, a_{n-1}b_{n-2},a_{n-1})$. Then $f_{\mathbf a} (x)=a_{n-1}h_1(x)h_2(x)\dots h_l(x)$ and by Lemma \ref{lm_factor}, $f_{\mathbf a}^* (x)=a_{n-1}h_1^*(x)h_2^*(x)\dots h_l^*(x)$. Therefore, \begin{align*} f_{\mathbf a} (x)f_{\mathbf a}^* (x) &=a_{n-1}^2h_1(x)h_2(x)\dots h_l(x)h_1^*(x)h_2^*(x)\dots h_l^*(x)\\ &=a_{n-1}^2(-1)^l h_1(x)h_2(x)\dots h_l(x)(-h_1^*(x))(-h_2^*(x))\dots (-h_l^*(x))\\ &=k\sum_{i=0}^{2n-2} x^i. \end{align*} Hence, $\mathbf a$ is a $(\overline k,p)$-sequence (Lemma \ref{lm_elementary_relation}). Finally, note that $a_{n-1}$ and $-a_{n-1}$ are roots of $x^2-(-1)^{n-1}k$. We may choose $q_i=h_i(x)$ or $-h_i^*(x)$ for $1\leq i\leq l$ and set $g_{\mathbf c}(x)=\pm a_{n-1}q_1(x)q_2(x)\dots q_l(x)$. Then $\mathbf c$ is also a $(\overline k,p)$-sequence. So, if such a sequence exists, there are exactly $2^l$ of them if $p=2$ and $2^{l+1}$ if $p$ is odd. This completes the proof of the theorem. \end{proof} Note that when $p=2$, Theorem \ref{thm_main} is the same as Theorem \ref{thm_basic_new}. So, Theorem \ref{thm_main} can be considered as a generalization of Theorem \ref{thm_basic_new}. Recall that $\mathbf y_k=(y_0,y_1,y_2,\dots )$ with $y_i=(-1)^ik$. If $k\equiv 0 \mod p$, then $\mathbf y_k=\overline 0$. This case has been considered in Corollary \ref{case_k_0}. So, we may assume $k\in\mathbb Z_p\setminus \{0\}$. If $p=2$, then $\mathbf y_k=\overline 1$. This case has been considered in Theorem \ref{thm_basic_new} and \ref{thm_main}. So, we may assume that $p$ is an odd prime. \begin{lm}\label{lm_monic_equiv} \ \begin{itemize} \item[\textnormal{(a)}] Suppose $n$ is odd. Then $\mathbf a=(a_0,a_1,\dots, a_{n-1})$ is a $(\overline k,p)$-sequence if and only if \newline $\mathbf b=(a_0,-a_1,\dots, (-1)^{n-1}a_{n-1})$ is a $(\mathbf y_k,p)$-sequence. \item[\textnormal{(b)}] Suppose $n$ is even. Then $\mathbf a=(a_0,a_1,\dots, a_{n-1})$ is a $(\overline {-k},p)$-sequence if and only if\newline $\mathbf b=(a_0,-a_1,\dots, (-1)^{n-1}a_{n-1})$ is a $(\mathbf y_k,p)$-sequence. \end{itemize} \end{lm} \begin{proof} By Lemma \ref{lm_elementary_relation}, $\mathbf b$ is a $(\mathbf y_k,p)$-sequence if and only if \begin{align*} f_{\mathbf b} (x)f_{\mathbf b}^* (x)&=\sum_{i=0}^{n-1} (-1)^{n-1-i}kx^i +x^{n-1}\sum_{i=1}^{n-1} (-1)^ikx^{i}\\ &=(-1)^{n-1}k\sum_{i=0}^{2n-2} (-1)^ix^i. \end{align*} Suppose $n$ is odd. Then $f_{\mathbf b} (x)f_{\mathbf b}^* (x)=k\sum_{i=0}^{2n-2} (-1)^ix^i$. By Lemma \ref{lm_elementary_relation}, $\mathbf a$ is a $(\overline k,p)$-sequence if and only if \begin{align*} f_{\mathbf a} (x)f_{\mathbf a}^* (x)=k\sum_{i=0}^{2n-2} x^i. \end{align*} Hence, part (a) of the lemma follows by noting that $f_{\mathbf b} (x)=f_{\mathbf a} (-x)$ and $f_{\mathbf a} (x)=f_{\mathbf b} (-x)$. Suppose $n$ is even. Then $f_{\mathbf b} (x)f_{\mathbf b}^* (x)=-k\sum_{i=0}^{2n-2} (-1)^ix^i$. By Lemma \ref{lm_elementary_relation}, $\mathbf a$ is a $(\overline {-k},p)$-sequence if and only if \begin{align*} f_{\mathbf a} (x)f_{\mathbf a}^* (x)=-k\sum_{i=0}^{2n-2} x^i. \end{align*} Hence, part (b) of the lemma follows by noting that $f_{\mathbf b} (x)=f_{\mathbf a} (-x)$ and $f_{\mathbf a} (x)=f_{\mathbf b} (-x)$. \end{proof} \begin{thm}\label{thm_main2} Let $p$ be an odd prime, $k\in\mathbb Z_p\setminus \{0\}$ and $\gcd(p,2n-1)=1=\gcd(p-1,2n-1)$. A $(\mathbf y_k,p)$-sequence of length $n> 1$ exists if and only if \begin{itemize} \item[\textnormal{(a)}] the order of $p$ is odd in $U_{2n-1}$, \item[\textnormal{(b)}] $k$ is a quadratic residue modulo $p$. \end{itemize} Furthermore, if such a sequence exists, then there are exactly $2^{l+1}$ of them, where $2l$ is the number of irreducible factors of $\sum_{i=0}^{2n-2} x^i$. \end{thm} \begin{proof} Suppose $n$ is odd. By part (a) of Lemma \ref{lm_monic_equiv}, there is a $(\mathbf y_k,p)$-sequence of length $n> 1$ if and only if there is a $(\overline k,p)$-sequence of length $n> 1$. Hence, Theorem \ref{thm_main2} follows from Theorem \ref{thm_main} by noting that $(-1)^{n-1}k=k$. Suppose $n$ is even. By part (a) of Lemma \ref{lm_monic_equiv}, there is a $(\mathbf y_k,p)$-sequence of length $n> 1$ if and only if there is a $(\overline {-k},p)$-sequence of length $n> 1$. Hence, Theorem \ref{thm_main2} follows from Theorem \ref{thm_main} by noting that $(-1)^{n-1}(-k)=k$. \end{proof} \begin{cor}\label{cor_condition} Let $p$ be a prime, $k\in\mathbb Z_p\setminus \{0\}$ and $\gcd(p,2n-1)=1=\gcd(p-1,2n-1)$. If there is a $(\overline k,p)$-sequence or a $(\mathbf y_k,p)$-sequence of length $n> 1$, then $p$ is a quadratic residue modulo $2n-1$. \end{cor} \begin{proof} By Theorem \ref{thm_main} or \ref{thm_main2}, the order of $p$ is odd in $U_{2n-1}$. Let $2e+1$ be the order of $p$. Then $(p^{e+1})^2\equiv p^{2e+2}\equiv p\mod (2n-1)$. Thus, $p$ is a quadratic residue modulo $2n-1$. \end{proof} Part (a) of the following Corollary was proved by Inglis and Wiseman \cite[Proposition 1]{Inglis}. It was asked by Alles \cite[Problem (1)]{Alles}. \begin{cor}\label{cor_small} Let $p$ be a prime, $k\in\mathbb Z_p\setminus \{0\}$ and $\gcd(p,2n-1)=1=\gcd(p-1,2n-1)$. Suppose there is a $(\overline k,p)$-sequence or a $(\mathbf y_k,p)$-sequence of length $n> 1$. Then \begin{itemize} \item[\textnormal{(a)}] $n\equiv 0$ or $1\mod 4$, if $p=2$; \item[\textnormal{(b)}] $n\equiv 0$ or $1\mod 6$, if $p=3$; \item[\textnormal{(c)}] $n\equiv 0$ or $1\mod 5$, if $p=5$; \item[\textnormal{(d)}] $n\equiv 0$, $1$, $10$, $13$, $15$, $16$, $19$, $24$, $27$, $28$, $30$, $33\mod 42$, if $p=7$. \end{itemize} \end{cor} \begin{proof} (a) By Corollary \ref{cor_condition}, $2$ is a quadratic residue modulo $2n-1$. Let $q$ be a prime appearing in the factorization of $2n-1$. Then $q$ is odd and $2$ is a quadratic residue modulo $q$. Therefore $q\equiv 1$ or $7\mod 8$. This implies that $2n-1\equiv 1$ or $7\mod 8$. Thus, $n\equiv 1$ or $0\mod 4$. \vskip 0.5cm \noindent (b) Since $\gcd(3,2n-1)=1$, we require $2n-1\equiv 1$ or $2\mod 3$, that is $n\equiv 1$ or $0\mod 3$. By Corollary \ref{cor_condition}, $3$ is a quadratic residue modulo $2n-1$. If $q$ is a prime appearing in the factorization of $2n-1$, then $q$ is odd and $3$ is a quadratic residue modulo $q$. By the Quadratic Reciprocity Law, $q\equiv \pm 1\mod 12$. This implies that $2n-1\equiv 1$ or $11\mod 12$. Thus, $n\equiv 1$ or $0\mod 6$. \vskip 0.5cm \noindent (c) Since $\gcd(5,2n-1)=1$, we require $2n-1\equiv 1$, $2$, $3$, or $4\mod 5$, that is $n\equiv 1$, $4$, $2$, or $0\mod 5$. As in part (b), if $q$ is a prime appearing in the factorization of $2n-1$, then $5$ is a quadratic residue modulo $q$. By the Quadratic Reciprocity Law, $q\equiv \pm 1\mod 5$. This implies that $2n-1\equiv 1$ or $4\mod 5$. Thus, $n\equiv 1$ or $0\mod 5$. \vskip 0.5cm \noindent (d) Since $\gcd(7,2n-1)=1$ and $\gcd(6,2n-1)=1$, $n\not \equiv 4\mod 7$ and $n\not\equiv 2\mod 3$. As before, if $q$ is a prime appearing in the factorization of $2n-1$, then $7$ is a quadratic residue modulo $q$. By the Quadratic Reciprocity Law, $q\equiv \pm 1$, $\pm 3$, or $\pm 9\mod 28$. This implies that $2n-1\equiv \pm 1$, $\pm 3$, or $\pm 9\mod 28$. Thus, $n\equiv 0$, $1$, $2$, $5$, $10$, or $13\mod 14$. Since $n\not\equiv 2\mod 3$ and $\gcd(3,14)=1$, we must have $n\equiv 0$, $28$, $1$, $15$, $16$, $30$, $19$, $33$, $10$, $24$, $13$ or $27\mod 42$. \end{proof} \section*{Acknowledgments} We would like to thank the anonymous referee for the comments that helped us make several improvements to this paper. This project was supported by the Frontier Science Research Cluster, University of Malaya (RG367-15AFR). \begin{thebibliography}{99} \bibitem{Alles} P. Alles, On a conjecture of J. Pelik\'an, {\em J. Combin. Theory Ser. A} {\bf 60} (1992), 312--313. \bibitem{Inglis} N.F.J. Inglis and J.D.A. Wiseman, Very odd sequences, {\em J. Combin. Theory Ser. A} {\bf 71} (1995), 89--96. \bibitem{Jacobson} N. Jacobson, {\em Basic Algebra I}, second edition, W.H. Freeman and Company, U.S.A., 1985. \bibitem{William} F.J. MacWilliams and A.M. Odlyzko, Pelikan's conjecture and cyclotomic cosets, {\em J. Combin. Theory Ser. A} {\bf 22} (1977), 110--114. \bibitem{Moree} P. Moree and P. Sol\'e, Around Pelik\'an's conjecture on very odd sequences, {\em Manuscripta Math.} {\bf 117}, (2005), 219--238. \bibitem{Pelikan} J. Pelik\'an, Contribution to ``Problems'', {\em Colloq. Math. Soc. J\'anos Bolyai} {\bf 10} p. 1549, North-Holland, Amsterdam, 1975. \end{thebibliography} \end{document} \end{document}