TITLE: Find the function $f(x)$ if $f(x+2)=f(x+1)+2f(x)$ for all $x\in \mathbb{Z}^{+}$
QUESTION [7 upvotes]: Here is my problem:

If $x\in \mathbb{Z}^{+}$ and $f(x+2)=f(x+1)+2f(x)$
  find the function $f(x)$
where, $f(1)=4, f(2)=2.$

When I encounter this problem, I thought the question is wrong. I obviously, I would expect a question like this, for example: $f(5)+f(17)=?$
Anyway, I did something like this:

$f(3)=f(2)+2f(1)$
$f(4)=f(3)+2f(2)=f(2)+2f(1)+2f(2)=3f(2)+2f(1)$
$f(5)=f(4)+2f(3)=3f(2)+2f(1)+2f(2)+4f(1)=5f(2)+6f(1)$
$f(6)=f(5)+2f(4)=5f(2)+6f(1)+6f(2)+4f(1)=11f(2)+10f(1)$
$f(7)=f(6)+2f(5)=11f(2)+10f(1)+10f(2)+12f(1)=21f(2)+22f(1)$
$f(8)=f(7)+2f(6)=21f(2)+22f(1)+22f(2)+20f(1)=43f(2)+42f(1)$

$A_{f(2)} :=\left\{ 1,3,5,11,21,43 ... \right\}$
$B_{f(1)} :=\left\{ 2,2,6,10,22,42 ... \right\}$
Here,  $A_{f(2)}$ and $B_{f(1)}$ are coefficients.
$A_{f_1(2)}=2^1-1; A_{f_2(2)}=2^2-2+1; A_{f_3(2)}=2^3-2^2+2-1;...; A_{f_n(2)}=2^n-2^{n-1}+2^{n-2}-2^{n-3}+2^{n-4}-2^{n-5}+...-...+ (-1)^n \Longrightarrow A_{f_n(1)}=\frac {2^{n+1}-2(-1)^{n+2}}{3}=\frac {2^{n+1}+2(-1)^{n+3}}{3}$
$B_{f_1(1)}=2^1; B_{f_2(1)}=2^2-2; B_{f_3(1)}=2^3-2^2+2;...;B_{f_n(1)}=2^n-2^{n-1}+2^{n-2}-2^{n-3}+2^{n-4}-2^{n-5}+...-...+2 (-1)^{n+1}  \Longrightarrow B_{f_n(2)}=\frac{2^{n+1}-(-1)^{n+1}}{3}=\frac{2^{n+1}+(-1)^{n+2}}{3}$
$f(n+2)=2A_{f_n(1)}+4B_{f_n(2)}=\frac {2^{n+1}+2(-1)^{n+3}}{3} ×2+ \frac{2^{n+1}+(-1)^{n+2}}{3} ×2^2=2^{n+2}-2(-1)^{n+2} \iff f(x)=2^x-2(-1)^x$
Finally, I got an answer like this:

$$f(x)=2^x+2(-1)^{x+1} , x\in \mathbb Z^{+}$$

Honestly, I don't know. Maybe, this is a ridiculous way. Because, it might be an intelligent way for to do it. And You know what I will actually asking. Is my solution correct? Or,was there an intelligent way to do it?
Thank you!

REPLY [2 votes]: Since $x\in \mathbb Z^{+}$, it is a second order linear difference equation. You can write it as:
$$y_{n+2}=y_{n+1}+2y_n, y_1=4,y_2=2, \ \ \ \text{find} \ \ y_n.$$
Use the method of generating functions.
Consider $f(x)=\sum_{n\ge 1}y_nx^n$. Multiply the given equation by $x^{n+2}$ and sum them:
$$\sum_{n\ge 1} y_{n+2}x^{n+2}=\sum_{n\ge 1}y_{n+1}x^{n+2}+\sum_{n\ge 1}2y_nx^{n+2} \Rightarrow \\
f(x)-y_2x^2-y_1x=x(f(x)-y_1x)+2x^2f(x) \Rightarrow \\
f(x)=\frac{4x-2x^2}{1-x-2x^2}=\frac{1}{1-2x}-\frac{2}{1+x}+1.$$
Now we need to find $y_n$ (the coefficients of the expansion of $f(x)$):
$$\begin{align}[x^n]f(x)&=[x^n](1-2x)^{-1}-2[x^n](1+x)^{-1}+0 =\\
&=[x^n]{-1\choose n}(-2x)^n-[x^n]2{-1\choose n}x^n=\\
&=[x^n]{1+n-1\choose n}(-1)^n(-2x)^n-[x^n]2{1+n-1\choose n}(-1)^nx^n=\\
&=[x^n]2^nx^n-[x^n]2\cdot (-1)^nx^n=2^n-2\cdot(-1)^n,\end{align}$$
where ${-n\choose r}={n+r-1\choose r}(-1)^r$.
Hence:
$$y_n=2^n-2\cdot (-1)^n.$$
or:
$$f(x)=2^x-2\cdot (-1)^x, x\in \mathbb Z^+.$$


TITLE: If a graph has a chromatic number $k$, then for any color there is a vertex of that color that has as neighbors all the other colors
QUESTION [4 upvotes]: Let $G$ a graph and $k= \chi(G)$. Prove that for all $k$-colorings of $G$ and for all colors
 $i \in \{1,\ldots,k\} $, there exists $u \in V(G)$ of color $i$ such that for every $j \in \{1,\ldots,k\}$ \ $i$, there exists $v \in N(u)$ of color $j$.
What I have to show is that for every color of the graph, there is always a vertex of that color so that it is a neighbor of all other colors.
I have tried to prove by contradiction. The contradiction would occur in that if there is no vertex for which this would be fulfilled then the chromatic number would be smaller. I start by saying "Let $C_{1}$ be the set of vertices of color graph $1$, so let's suppose that ..." and there's the problem, I really do not know whether to suppose that there is a vertex that has all colors as neighbors except him same and another different, or that all the vertices in $C_{1}$ fulfil this property, or if some, etc, I am totally confused.
The other way is by induction, the base step would be for two or more (considering that the graph is not a single vertex) but I do not know how to use the induction hypothesis to prove the case of $k + 1$ colors.
I would appreciate any help.

REPLY [2 votes]: First, observe that there is a small glitch in the statement of the problem. "Prove that for all $k$-colorings of $G$ and for all colors $i \in \{1,\ldots,k\} \setminus \{i\}$,..." should not have the "$\setminus \{i\}$" at the end.  The claim is about every $k$-coloring and every color.
Next, the idea of proving the claim by contradiction is a good one, as shown in @mathnoob's answer.  You were on the right track, but then got confused.  This is likely due to the fact that the claim you try to prove has several quantifiers in it: for all colorings, for all colors, there exists a vertex, such that for every other color....
In cases like these, it's useful, especially if you are realtively new to proofs, to start by writing down the negation of the claim you want to prove.  Let's do it for the problem at hand:
Suppose there exist a $k$-coloring of $G$ and a color $i \in \{1,\ldots,k\}$ such that, for every vertex $u \in V(G)$ of color $i$, there exists a color $j \in \{1,\ldots,k\} \setminus \{i\}$ such that no vertex $v \in N(u)$ has color $j$.
This unambiguously states the assumption that is supposed to lead to a clash with the assumption that $\chi(G) = k$.  In fact, as pointed out in @mathnoob's answer, you can change the color of $u$ from $i$ to $j$ while preserving a valid coloring.  Once this has been done for all vertices of color $i$, the resulting coloring has $k-1$ colors: contradiction!


TITLE: Easy Double Sums Question: $\sum_{m=1}^{\infty} \sum_{n=1}^{\infty} \frac{1}{(m+n)!}$
QUESTION [5 upvotes]: How to calculate $\sum_{m=1}^{\infty} \sum_{n=1}^{\infty} \dfrac{1}{(m+n)!} $ ?
I don't know how to approach it . Please help :)
P.S.I am new to Double Sums and am not able to find any good sources to study it , can anyone help please ?

REPLY [0 votes]: \begin{align}
&\sum_{m=1}^\infty \sum_{n=1}^\infty \frac1{(m+n)!}\\
=& \sum_{n=1}^\infty \frac1{(1+n)!} + \sum_{n=1}^\infty \frac1{(2+n)!} + \sum_{n=1}^\infty \frac1{(3+n)!} + \dots\\
=&\vphantom{+}\frac1{2!} + \frac1{3!} + \frac1{4!} + \frac1{5!} + \dots\\
 &+\frac1{3!} + \frac1{4!} + \frac1{5!} + \frac1{6!} + \dots\\
 &+\frac1{4!} + \frac1{5!} + \frac1{6!} + \frac1{7!} + \dots
\end{align}
Let's add and subtract $\sum\limits_{j=1}^\infty \frac1{j!}$. It doesn't change the sum and it's easier to add.
\begin{align*}
=&\left(\frac1{1!}+\color{red}{\frac1{2!}}+\color{green}{\frac1{3!}}+\color{blue}{\frac1{4!}}+\dots\right.\\
&+\color{red}{\frac1{2!}}+\color{green}{\frac1{3!}}+\color{blue}{\frac1{4!}}+\frac1{5!}+\dots\\
&+\color{green}{\frac1{3!}}+\color{blue}{\frac1{4!}}+\frac1{5!}+\frac1{6!}+\dots\\
&+\color{blue}{\frac1{4!}}+\frac1{5!}+\frac1{6!}+\frac1{7!}+\dots\\
&\left.\vphantom{\frac12}+\dots\right)\\
&-\frac1{1!}-\frac1{2!}-\frac1{3!}-\frac1{4!}-\dots\\
&=\left(1+\color{red}{\frac1{1!}}+\color{green}{\frac1{2!}}+\color{blue}{\frac1{3!}}+\dots\right)-\left(\frac1{1!}+\frac1{2!}+\frac1{3!}+\dots\right)=\boxed{1}
\end{align*}
Hope this helps! I know that the adding and subtracting $\sum\frac1{j!}$ came out of nowhere, but it works.


TITLE: Math videos containing real time rough thinking
QUESTION [31 upvotes]: I find this vlog experiment of Gowers very brave, and I think his idea of having examples of real-time mathematical thinking by experts can be very encouraging for young mathematicians, who imagine the pace of the greats is impossibly far and away above that of mere mortals when they meet new problems. (Online comments by Borcherds, as well as this wonderfully courageous experiment by Gowers suggest otherwise.) A funny anecdote along these lines: Once a graduate student said to me: "I have an image of Terry Tao eating his breakfast one morning, eating his cereal, and as he lifts his spoon to his mouth he pauses, looks off into the distance, and in that moment does more productive mathematics than I will in my entire lifetime."
Have others participated in this experiment? Are there other online video examples of "real time raw thinking" by leading mathematicians, following up on Gowers's experiment above?
Whether this question should be on MO is undoubtedly going to be controversial but I think it has to do with mathematical practice, and particularly the working styles of top mathematicians who frequent this forum.

REPLY [12 votes]: When I taught a beginners course in analysis a few years ago I wanted to give the students an impression of how one can work on exam problems. I asked somebody to prepare a test exam (I had my exam prepared already and asked for an exam in a similar style). I got the exam in a closed envelope and walked into an empty lecture hall with a blackboard and document camera. There I recorded myself solving the exam problems thinking out loud all the time. I first went through the problems, commented on then, then went to the blackboard and started solving them and once I was seeing how I should do it, I went to the document camera and wrote down the solution as I would write them to get full marks. I posted the video uncut for the students. It was actually a nice experience for me and I got a lot of feedback saying that this was very helpful for the preparation of the exam (and also it helped some people with "test anxiety" - if that is the correct word in English…).

REPLY [6 votes]: I feel that after what I said I should offer something constructive here as well. Part of the problem with such movies is that the very act of verbalizing the thought process interferes with it quite severely. At the very least it significantly slows you down (take any computer program you ever wrote for computing something interesting, add the command to print the result after every operation, and watch it running). But that is not all. Interrupting a human thought is worse than interrupting a computer program because most of us are incapable of storing a SSW at the moment of interruption and retrieving it without error once the interruption is over. Also, when talking, we feel like we need to exhibit some clear logic in our transitions, while in fact many of them occur merely because one chain of thoughts suddenly outpaces the other, so we just switch to a more promising approach, and so on, and so forth.
So, simultaneous verbalization is a killer. What to do then? The only way out I see is to think it all through in the usual way and then post all that we wrote on paper in the order of writing with some short comments about the places that would look totally unclear to an outsider. That is like having a fossil record of your thought that tells about it as much as fragments of dinosaur bones about the terrible lizards themselves, which is not everything, but still quite a lot. Here is mine for the same problem. What I had in front of my eyes at the moment of writing was the screen with 4 first determinants, out of which only the last one really mattered, i.e., I was looking at
$$
\begin{matrix}
1&1&1&1
\\
1&2&3&4
\\
1&3&6&10
\\
1&4&10&20
\end{matrix}
$$
What I wrote is here:

(the top scribbled line reads "row - part. sums of prev. rows?").
The rest should be clear from my comments.
I feel like I have to add in the end that it doesn't mean that my thinking is better than that of Gowers. In fact, IMHO, compared to him, I am a hopeless imbecile sliding into senility. It merely means that I believe that the movie he posted does not (and, as conceived, could possibly not) reflect his true thinking. Also, to speak frankly, the Terry Tao's blog post titled "Does one have to be a genius to do maths?" reminds me of the phrase "Superman just helps now and then" in the famous cartoon. It is all fine, but if you watch that cartoon with a timer in hand, you'll realize that this "now and then" occupies about 90% of the shown events and the corresponding percentage in Terry's published papers is fairly close. As to his "generals", his account, if you translate it into layman language, reads to me "On my test I had to jump over the Empire State building and I almost knocked the spire off plus made a couple of unnecessary extra steps when landing, which showed to me that I need some more training before I attempt an unaided flight to the stratosphere". Disagree? Then try to pass his test yourself right now. You have enough information about what the questions were in his post, so just sit down and honestly write the answers to the best of your abilities. If you get happy with the result, let me know. I'm willing to take your word for it. But I give you mine that I failed miserably :-)
I am as curious about how great minds work as the OP, so if somebody has a good idea of how to observe that thought process, I will be happy to hear it. I also admire Tim Gowers for his attempt despite the fact that I still firmly believe that the way he approached it was hopelessly doomed from the beginning unless the true goal was very different from the proclaimed one.


TITLE: Recent missed opportunities à la Freeman Dyson
QUESTION [5 upvotes]: There is an excellent paper by Freeman Dyson from 1972 (here) and therein the author cites old talks by Hilbert (here) and Minkowski (chapter 2 here) speaking about similar topics, namely how opportunities for discoveries could be better if mathematicians and physicist worked more closely.
I wanted to ask if there are recent publications (roughly > 2000) of that type?

REPLY [1 votes]: I'm surprised Freeman Dyson didn't mention Emmy Noether, a German mathematician, and her contribution to the conceptual structures of the mathematics in modern physics in his paper. Nina Byers goes into this in detail in her paper "E. Noether’s Discovery of the Deep Connection Between Symmetries and Conservation Laws" in 1998.
https://arxiv.org/abs/physics/9807044v2
"Though the general theory of relativity was completed in 1915, there remained unresolved problems. In particular, the principle of local energy conservation was a vexing issue. In the general theory, energy is not conserved locally as it is in classical field theories - Newtonian gravity, electromagnetism, hydrodynamics, etc.. Energy conservation in the general theory
has been perplexing many people for decades. In the early days, Hilbert wrote about this problem as ‘the failure of the energy theorem’. In a correspondence with Klein [3], he asserted that this ‘failure’ is a characteristic feature of the general theory, and that instead of ‘proper energy theorems’ one had ‘improper energy theorems’ in such a theory. This
conjecture was clarified, quantified and proved correct by Emmy Noether."
https://en.wikipedia.org/wiki/Emmy_Noether


TITLE: a divisibility problem
QUESTION [3 upvotes]: if $a$ is an integer , such that it is not divisible by 2 or 3, prove that $ 24 $ divides $ a^2+ 23$ .
I took cases ,case $1$ : when $a$ is divisible by only $2$ and not $3$ then we can write  $a = 6k+2, 6k+4 $ and case 2: when $a= 6k+3$ and here $a$ is divisible by only $3$ and not $2$.
and then in each case,
I substituted values of $a$ in $a^2+23$ , but got nothing. I do think my case by- case analysis here is wrong, but surely I'm missing something .
please help by suggesting how can I improve my solution. No need to give me an elegant solution, only a few hints will be fine.

REPLY [1 votes]: If a does not divide neither 2 nor 3, it does not divide 6. So , working with k, we see a must be of one of the forms $6k+1$ , or $6k-1$ , since $6k+2=2(3k+1), 6k+4=2(3k+2)$, etc.
Consider the first case, $a=6k+1$; then:
$a^2+23=(6k+1)^2+23=36k^2+12k+1+23=36k^2+12k+24=12k(3k+1)+24$ . But$k$ and $3k+1$ will
always have different parity, i.e., if $k$ is even, then $3k+1$ is odd--and viceversa.  So we have the cases:
1)If $k$ is even, we're done, since then:
$12k(3k+1)+24=12(2k')(3k+1)=24k'(3k+1)+24$
2)If $k$ is odd, then $3k+1$ is even, say $3k+1=2k''$, then:
$12k(3k+1)+24=12k(2k'')+24=24kk''+24$
The case for a=6k-1 is similar.


TITLE: A question about Cantor's Power Set theorem without the Axiom of Choice
QUESTION [3 upvotes]: Assume that we are working in ZF set theory without the Axiom of Choice. If S is an infinite set, let $S(f)$ denote the set of all finite subsets of $S$, let $S(I)$ denote the set of all infinite subsets of $S$ and let $\operatorname{Card}(S)$ denote the cardinal number of $S$.
Even though we can prove Cantor's theorem which states that the Power Set of $S$ always has a greater cardinal number than $\operatorname{Card}(S)$, could there exist an uncountable set $X$ such that we could not disprove the statement $\operatorname{Card}(X)=\operatorname{Card}(X(f))=\operatorname{Card}(X(I))$?
The answer would, of course, be negative if-without the Axiom of Choice-one could prove in ZF that, given any infinite set $S$, $\operatorname{Card}(S(I))$ is always greater than $\operatorname{Card}(S)$. Is this possible?

REPLY [5 votes]: For the first equality, the answer is true.
It is quite easy to construct examples where the set of finite subsets is strictly larger. For example if $X$ is an infinite Dedekind-finite set which is the countable union of finite sets (e.g. Russell socks sets), then the set $X(f)$ is not Dedekind-finite anymore, since there is a countably infinite subset to it.
Finally, $\operatorname{Card}(X)=\operatorname{Card}(X(I))$ is provably false, unless $X=\varnothing$, in which case both cardinals are $0$. And if $X$ is non-empty finite, then $X(I)$ is empty while $X$ is not, so there is no equality.
If $\operatorname{Card}(X)=\operatorname{Card}(X(I))$, then $\operatorname{Card}(\mathcal P(X))=\operatorname{Card}(X(I))+\operatorname{Card}(X(f))=\operatorname{Card}(X)+\operatorname{Card}(X(f))$.
But since if $X$ is infinite, then there is at least an injection from the finite subsets to the infinite subsets: $A\mapsto X\setminus A$. So it follows that $\operatorname{Card}(X(f))=\operatorname{Card}(X(I))$ so we have:
$$\operatorname{Card}(\mathcal P(X))=2\cdot\operatorname{Card}(X)$$
But this is a contradiction, since if $\operatorname{Card}(X)>4$, then $$2\cdot\operatorname{Card}(X)<2^{\operatorname{Card}(X)}=\operatorname{Card}(\mathcal P(X)).$$ (See here for a sketch of the proof of that last inequality.)


text:
\section{Experiments} \label{sec:ex}

In this section we implement our algorithm on various kinds of distributed networks corresponding to randomly generated systems of equations and systems perturbed from an orthogonal coefficient matrix. The latter illustrates the point of Remark \ref{spectralnormone}. Specifically, we analyze two scenarios: (1) comparing different subnetwork structures for a given network and (2) comparing different network structures for a given system of equations.

For the first experiment, we consider a 7-node binary network and compare leaf subnetworks to extended subnetworks as depicted in Figure \ref{fig:subnetworks}. We assign the relaxation parameters as follows: set $\omega_v = 1.5$ if the node $v$ is not associated with a subnetwork; set $\omega_v = \omega$ if the node $v$ belongs to a subnetwork. Then we calculate the spectral radius of the operator $P^{\vec{\omega}}$ as a function of $\omega$. For a baseline, we include the spectral radius of the network with no subnetwork structures in this set-up, which we label uniform.

\begin{figure*}[h!]
    \centering
    \begin{subfigure}[h]{0.5\textwidth}
        \centering

        \begin{tikzpicture}

        \def\w{0.8}
        \def\u{0.4}

        \node[circle,fill=black!20!white] (1d) at (-3*\w,-6*\u) {1};
        \node[circle,fill=black!20!white] (2d) at (-4.5*\w,-8*\u) {2};
        \node[circle,fill=black!20!white] (3d) at (-1.5*\w,-8*\u) {3};
        \node[circle,fill=black!20!white] (4d) at (-5.25*\w,-10.5*\u) {4};
        \node[circle,fill=black!20!white] (5d) at (-3.75*\w,-10.5*\u) {5};
        \node[circle,fill=black!20!white] (6d) at (-2.25*\w,-10.5*\u) {6};
        \node[circle,fill=black!20!white] (7d) at (-0.75*\w,-10.5*\u) {7};

        \draw (1d) to (3d);
        \draw (1d) to (2d);
        \draw (2d) to (4d);
        \draw (2d) to (5d);
        \draw (3d) to (6d);
        \draw (3d) to (7d);

        \draw[black,thick,dashed] (-4.5*\w,-10.5*\u)
        ellipse (1.5*\w cm and 1.25*\u cm);
        \draw[black,thick,dashed] (-1.5*\w,-10.5*\u)
        ellipse (1.5*\w cm and 1.25*\u cm);

        \end{tikzpicture}

        \caption{Leaf subnetworks}
    \end{subfigure}
    ~
    \begin{subfigure}[h]{0.5\textwidth}
        \centering

        \begin{tikzpicture}

        \def\w{0.8}
        \def\u{0.4}

        \node[circle,fill=black!20!white] (1d) at (-3*\w,-6*\u) {1};
        \node[circle,fill=black!20!white] (2d) at (-4.5*\w,-8*\u) {2};
        \node[circle,fill=black!20!white] (3d) at (-1.5*\w,-8*\u) {3};
        \node[circle,fill=black!20!white] (4d) at (-5.25*\w,-10.5*\u) {4};
        \node[circle,fill=black!20!white] (5d) at (-3.75*\w,-10.5*\u) {5};
        \node[circle,fill=black!20!white] (6d) at (-2.25*\w,-10.5*\u) {6};
        \node[circle,fill=black!20!white] (7d) at (-0.75*\w,-10.5*\u) {7};

        \draw (1d) to (3d);
        \draw (1d) to (2d);
        \draw (2d) to (4d);
        \draw (2d) to (5d);
        \draw (3d) to (6d);
        \draw (3d) to (7d);

        \draw[black,thick,dashed] (-4.5*\w,-9.5*\u)
        ellipse (1.5*\w cm and 2.5*\u cm);
        \draw[black,thick,dashed] (-1.5*\w,-9.5*\u)
        ellipse (1.5*\w cm and 2.5*\u cm);

        \end{tikzpicture}

        \caption{Extended subnetworks}
    \end{subfigure}
    \caption{The 7-node binary network with its subnetworks}
    \label{fig:subnetworks}
\end{figure*}

\begin{figure}[h!]
    \centering
    \includegraphics[scale = 0.325]{ext_specradii.jpg}
    \caption{Spectral radius of $P^{\vec{\omega}}$ for two subnetwork structures. The dashed line represents a network with uniformly distributed relaxation parameters $\omega = 1.5$.}
\end{figure}

The numerical experiments suggest that the leaf subnetwork structures are more practical than the extended subnetwork structures for two reasons. In general, the spectral radius of $P^{\vec{\omega}}$ is decreasing for $\omega$ slightly larger than $1.5$ and is, therefore, comparatively smaller than the baseline established by the uniform case in which all of the parameters are set to 1.5. In this situation, we find that the spectral radius tends to be smaller than the baseline for relatively large relaxation parameters in the case of the leaf subnetwork structures and less so in the case of the extended subnetwork structures. This implies that parameter selection is more reliable for leaf subnetworks than for their extended counterparts. Second, the spectral radius is often smaller for leaf subnetworks when the parameters are large. We believe that these observations are a consequence of the pooling stage which is a poor method of producing the next iterate in the distributed Kaczmarz algorithm from the leaf estimates. The depth of the extended network increases the number of overrelaxed projections, often leading to adverse results in the pooling stage.

\begin{figure*}[h!]
    \centering
    \begin{subfigure}[t]{0.5\textwidth}
        \centering
        \begin{tikzpicture}

        \def\w{0.8}
        \def\u{0.4}

        \node[circle,fill=black!20!white] (1d) at (-3*\w,-6*\u) {1};
        \node[circle,fill=black!20!white] (2d) at (-4.5*\w,-8*\u) {2};
        \node[circle,fill=black!20!white] (3d) at (-1.5*\w,-8*\u) {3};
        \node[circle,fill=black!20!white] (4d) at (-5.25*\w,-10.5*\u) {4};
        \node[circle,fill=black!20!white] (5d) at (-3.75*\w,-10.5*\u) {5};

        \draw (1d) to (3d);
        \draw (1d) to (2d);
        \draw (2d) to (4d);
        \draw (2d) to (5d);

        \end{tikzpicture}
        \caption{Network I}
    \end{subfigure}
    ~
    \begin{subfigure}[t]{0.5\textwidth}
        \centering
        \begin{tikzpicture}

        \def\w{0.8}
        \def\u{0.4}

        \node[circle,fill=black!20!white] (1d) at (-3*\w,-6*\u) {1};
        \node[circle,fill=black!20!white] (2d) at (-4.5*\w,-8*\u) {2};
        \node[circle,fill=black!20!white] (3d) at (-1.5*\w,-8*\u) {3};
        \node[circle,fill=black!20!white] (4d) at (-4.5*\w,-10.5*\u) {4};
        \node[circle,fill=black!20!white] (5d) at (-1.5*\w,-10.5*\u) {5};

        \draw (1d) to (3d);
        \draw (1d) to (2d);
        \draw (2d) to (4d);
        \draw (3d) to (5d);

        \end{tikzpicture}
        \caption{Network II}
    \end{subfigure}
    \caption{Two networks for a system of five equations}
    \label{fig:5nodenetworks}
\end{figure*}

For the second experiment, we consider the different network structures given in Figure \ref{fig:5nodenetworks} for a system of five equations. We compare the network structures for two kinds of systems: (1) entries of $A$ are randomly selected from a uniform distribution over $[0,1]$ and (2) $A$ is nearly orthogonal by perturbing the identity. Further, the entries of $\vec{b}$ are also randomly selected from a uniform distribution over $[0,1]$. We present results of numerical experiments for the nearly orthogonal system in Table \ref{table:orthogonal} and for the random system in Table \ref{table:random}. We include the optimal relaxation parameters that yield the minimum spectral radius along with an error estimate of an iterate using the optimal parameters. Figure \ref{fig:specradi_orth} shows how the spectral radius varies with respect to the relaxation parameter for networks I and II with leaf subnetworks. For network I, $\omega_1$ is on node 3, and $\omega_2$ is on the leaf subnetwork composed of nodes 4 and 5. For network II, $\omega_1$ is on node 5, and $\omega_2$ is on node 4.

\begin{table}[h!]
    \centering
    \begin{tabular}{c|c|c|c|c|c}
        & \multicolumn{3}{c|}{Leaf subnetworks} & \multicolumn{2}{c}{Uniform} \\
        \hline
        Network Type & ($\omega_1$, $\omega_2$)$_{\text{opt}}$ & $\rho(P^{\vec{\omega}})$ & $\|A\vec{x}^{(10)} - \vec{b}\|$ & $\rho(P^{\vec{\omega}})$ & $\|A\vec{x}^{(10)} - \vec{b}\|$ \\
        \hline
        I & (2.27,\,3.93) & 0.36532 & 3.479e-4 & 0.66617 & 3.6441e-3 \\
        \hline
        II & (1.49,\,2.52) & 0.37492 & 3.4554e-4 & 0.47598 & 5.7009e-4 \\
        \hline
    \end{tabular}
    \vspace{0.5cm}
    \caption{Comparing networks I and II for a nearly orthogonal system}
    \label{table:orthogonal}
\end{table}

\begin{table}[h!]
    \centering
    \begin{tabular}{c|c|c|c|c|c}
        & \multicolumn{3}{c|}{Leaf subnetworks} & \multicolumn{2}{c}{Uniform} \\
        \hline
        Network Type & ($\omega_1$, $\omega_2$)$_{\text{opt}}$ & $\rho(P^{\vec{\omega}})$ & $\|A\vec{x}^{(1500)} - \vec{b}\|$ & $\rho(P^{\vec{\omega}})$ & $\|A\vec{x}^{(1500)} - \vec{b}\|$ \\
        \hline
        I & (7.92,\,8.06) & 0.98844 & 1.5743e-8 & 0.99626 & 1.7049e-3 \\
        \hline
        II & (4.57,\,3.90) & 0.99512 & 8.3191e-4 & 0.99619 & 1.3288e-3 \\
        \hline
    \end{tabular}
    \vspace{0.5cm}
    \caption{Comparing networks I and II for a random system}
    \label{table:random}
\end{table}

\begin{figure*}[h!]

    \centering
    \begin{subfigure}[t]{0.5\textwidth}
        \centering
        \includegraphics[scale=0.3]{5nodetree_4_orth.jpg}
        \caption{Network I}
    \end{subfigure}
    ~
    \begin{subfigure}[t]{0.5\textwidth}
        \centering
        \includegraphics[scale=0.3]{5nodetree_9_orth.jpg}
        \caption{Network II}
    \end{subfigure}
    \caption{Spectral radii for a nearly orthogonal system}
    \label{fig:specradi_orth}
\end{figure*}

For both the nearly orthogonal and random systems, we see that the relaxation parameter is allowed to be larger than 2 to achieve convergence. Note also that the spectral radius $\rho(P^{\vec{\omega}})$ for systems with leaf subnetworks is smaller than the uniform system; hence we see better performance. For the nearly orthogonal systems with leaf subnetworks, we do not need many iterations of the algorithm to achieve a smaller error than the uniform system. However, for the random system, we need many more iterations to achieve this smaller error.

\begin{comment}

section we implement the methods that have been previously described. Several numerical experiments are described, and results are discussed. All codes were written in the Python language. For generality, a tree class was created to describe the experiments. Our class has a weight at each vertex, a parent if it is not the root, and a list of children for each vertex.

We calculate the spectral radius of $P$ to compare the rates of convergence. Recall that by its construction, the matrix $P$ is dependent on the stucture of the tree. For practical purposes, we also wish to consider parallel computing in the analysis. To do so, we consider the quantity $\rho^{m/h}$. Here, $\rho$ is the spectral radius of $P$, $h$ is the height of the tree, and $m$ is the number of vertices (or nodes) on that tree.

We set up the experiments as follows: We first fix a relaxation parameter $\omega$ on all internal nodes. For each experiment, we run four separate tests. The first test does not implement grouping. In the second test and third test, we implement leaf groupings. For the second test, $\omega = 0.75\omega_{max}$ on each leaf group. We do the same in the third test with $\omega = 0.875\omega_{max}$. As a fourth test for comparison, we consider a path graph with uniform relaxation parameter $\omega$. Below is a list of the fixed $\omega$ we considered:

\begin{enumerate}
    \item Experiment 1: $\omega = 1$
    \item Experiment 2: $\omega = 1.5$
    \item Experiment 3: $\omega = 1.75$
    \item Experiment 4: $\omega = 1.9$
\end{enumerate}

For each experiment, we wish to consider trees with 5-80 nodes. We used the Python tree class to randomly generate 10 trees for each of each size. For each of these trees, we considered 100 random systems of linear equations. The coefficients of these linear equations were randomly generated using a uniform distribution in the interval $[-5,\,5]$.

The results of these experiments are given in the figures below. \textbf{Include figures} \\

We now consider a few examples to demonstrate the idea of grouping subtrees.

\subsection{Example 1} First, we only consider trees with five nodes. In total, there are only nine non-isomorphic roots trees with five vertices. These are given in Table \ref{tab:five_trees}.

{
\centering
\begin{table}[!h]
    \begin{tabular}{|>{\centering\arraybackslash}m{.008\linewidth}|>{\centering\arraybackslash}m{.23\linewidth}|>{\centering\arraybackslash}m{.23\linewidth}|>{\centering\arraybackslash}m{.22\linewidth}|>{\centering\arraybackslash}m{.18\linewidth}|}
        \hline
         & \textbf{A} & \textbf{B} & \textbf{C} & \textbf{D} \\
         \hline
        \textbf{1} &

        \begin{tikzpicture}

        \def\w{1.0}
        \def\u{0.50}

        \node[circle,fill=teal!40!white] (1a) at (-4*\w,0*\u) [label=left:1]{};
        \node[circle,fill=teal!20!white] (2a) at (-5.15*\w,-3*\u) [label=left:2]{};
        \node[circle,fill=teal!20!white] (3a) at (-4.35*\w,-3*\u) [label=left:3]{};
        \node[circle,fill=teal!20!white] (4a) at (-3.65*\w,-3*\u)[label=left:4]{};
        \node[circle,fill=teal!20!white] (5a) at (-2.85*\w,-3*\u)[label=left:5]{};

        \draw[->] (1a) to (2a);
        \draw[->] (1a) to (3a);
        \draw[->] (1a) to (4a);
        \draw[->] (1a) to (5a);

        \end{tikzpicture}
&
        \begin{tikzpicture}

        \def\w{1.0}
        \def\u{0.50}

        \node[circle,fill=teal!40!white] (1b) at (0*\w,0*\u) [label=left:1]{};
        \node[circle,fill=teal!20!white] (2b) at (0*\w,-2*\u) [label=left:2]{};
        \node[circle,fill=teal!20!white] (3b) at (-0.75*\w,-4*\u)[label=left:3]{};
        \node[circle,fill=teal!20!white] (4b) at (0*\w,-4*\u) [label=left:4]{};
        \node[circle,fill=teal!20!white] (5b) at (0.75*\w,-4*\u) [label=left:5]{};
        \node[circle,fill=white!20!white] (6b) at (0*\w,1*\u){};

        \draw[->] (1b) to (2b);
        \draw[->] (2b) to (3b);
        \draw[->] (2b) to (4b);
        \draw[->] (2b) to (5b);

        \end{tikzpicture}

& - & - \\
        \hline
        \textbf{2} &

        \begin{tikzpicture}

        \def\w{1.0}
        \def\u{0.50}

        \node[circle,fill=red!40!white] (1c) at (-6*\w,-6*\u) [label=left:1]{};
        \node[circle,fill=red!20!white] (2c) at (-6*\w,-8*\u) [label=left:2]{};
        \node[circle,fill=red!20!white] (3c) at (-6*\w,-10*\u) [label=left:3]{};
        \node[circle,fill=red!20!white] (4c) at (-6.75*\w,-12*\u) [label=left:4]{};
        \node[circle,fill=red!20!white] (5c) at (-5.25*\w,-12*\u) [label=left:5]{};

        \draw[->] (1c) to (2c);
        \draw[->] (2c) to (3c);
        \draw[->] (3c) to (4c);
        \draw[->] (3c) to (5c);

        \end{tikzpicture}
&
        \begin{tikzpicture}

        \def\w{1.0}
        \def\u{0.50}

        \node[circle,fill=red!40!white] (1d) at (-3*\w,-6*\u) [label=left:1]{};
        \node[circle,fill=red!20!white] (2d) at (-3.75*\w,-8*\u) [label=left:2]{};
        \node[circle,fill=red!20!white] (3d) at (-2.25*\w,-8*\u) [label=left:3]{};
        \node[circle,fill=red!20!white] (4d) at (-4.5*\w,-10*\u) [label=left:4]{};
        \node[circle,fill=red!20!white] (5d) at (-3*\w,-10*\u) [label=left:5]{};

        \draw[->] (1d) to (3d);
        \draw[->] (1d) to (2d);
        \draw[->] (2d) to (4d);
        \draw[->] (2d) to (5d);

        \end{tikzpicture}
&
        \begin{tikzpicture}

        \def\w{1.0}
        \def\u{0.50}

        \node[circle,fill=red!40!white] (1e) at (0*\w,-6*\u) [label=left:1]{};
        \node[circle,fill=red!20!white] (2e) at (-1*\w,-8*\u) [label=left:2]{};
        \node[circle,fill=red!20!white] (3e) at (0*\w,-8*\u) [label=left:3]{};
        \node[circle,fill=red!20!white] (4e) at (1*\w,-8*\u) [label=left:4]{};
        \node[circle,fill=red!20!white] (5e) at (0*\w,-10*\u)[label=left:5]{};

        \draw[->] (1e) to (2e);
        \draw[->] (1e) to (3e);
        \draw[->] (1e) to (4e);
        \draw[->] (3e) to (5e);

        \end{tikzpicture}
&

        \begin{tikzpicture}

        \def\w{1.0}
        \def\u{0.50}

        \node[circle,fill=red!40!white] (1f) at (2*\w,-6*\u) [label=left:1]{};
        \node[circle,fill=red!20!white] (2f) at (2*\w,-8*\u) [label=left:2]{};
        \node[circle,fill=red!20!white] (3f) at (1.25*\w,-10*\u) [label=left:3]{};
        \node[circle,fill=red!20!white] (4f) at (2.75*\w,-10*\u) [label=left:4]{};
        \node[circle,fill=red!20!white] (5f) at (2.75*\w,-12*\u) [label=left:5]{};

        \draw[->] (1f) to (2f);
        \draw[->] (2f) to (3f);
        \draw[->] (2f) to (4f);
        \draw[->] (4f) to (5f);

        \end{tikzpicture}\\

        \hline
        \textbf{3} &
        \begin{tikzpicture}

        \def\w{1.0}
        \def\u{0.50}

        \node[circle,fill=blue!40!white] (1g) at (-7*\w,-14*\u) [label=left:1]{};
        \node[circle,fill=blue!20!white] (2g) at (-7*\w,-16*\u) [label=left:2]{};
        \node[circle,fill=blue!20!white] (3g) at (-7*\w,-18*\u) [label=left:3]{};
        \node[circle,fill=blue!20!white] (4g) at (-7*\w,-20*\u) [label=left:4]{};
        \node[circle,fill=blue!20!white] (5g) at (-7*\w,-22*\u) [label=left:5]{};

        \draw[->] (1g) to (2g);
        \draw[->] (2g) to (3g);
        \draw[->] (3g) to (4g);
        \draw[->] (4g) to (5g);

        \end{tikzpicture}
        &
        \begin{tikzpicture}

        \def\w{1.0}
        \def\u{0.50}

        \node[circle,fill=blue!40!white] (1h) at (-4*\w,-14*\u) [label=left:1]{};
        \node[circle,fill=blue!20!white] (2h) at (-4.75*\w,-16*\u) [label=left:2]{};
        \node[circle,fill=blue!20!white] (3h) at (-3.25*\w,-16*\u) [label=left:3]{};
        \node[circle,fill=blue!20!white] (4h) at (-3.25*\w,-18*\u) [label=left:4]{};
        \node[circle,fill=blue!20!white] (5h) at (-3.25*\w,-20*\u) [label=left:5]{};

        \draw[->] (1h) to (2h);
        \draw[->] (1h) to (3h);
        \draw[->] (3h) to (4h);
        \draw[->] (4h) to (5h);

        \end{tikzpicture}

        &
        \begin{tikzpicture}

        \def\w{1.0}
        \def\u{0.50}

        \node[circle,fill=blue!40!white] (1i) at (1.75*\w,-14*\u)[label=left:1]{};
        \node[circle,fill=blue!20!white] (2i) at (1.00*\w,-16*\u) [label=left:2]{};
        \node[circle,fill=blue!20!white] (3i) at (2.5*\w,-16*\u) [label=left:3]{};
        \node[circle,fill=blue!20!white] (4i) at (1.00*\w,-18*\u) [label=left:4]{};
        \node[circle,fill=blue!20!white] (5i) at (2.5*\w,-18*\u) [label=left:5]{};

        \draw[->] (1i) to (2i);
        \draw[->] (1i) to (3i);
        \draw[->] (2i) to (4i);
        \draw[->] (3i) to (5i);

        \end{tikzpicture}

        & - \\
        \hline
    \end{tabular}
    \caption{Rooted non-isomorphic trees with five vertices}
    \label{tab:five_trees}
\end{table}
}

For the internal nodes, we randomly select a relaxation parameter $\omega \in (1.5,\,2)$. For a sibling group, we randomly select $\omega \in (1.5,\, \omega_{max})$. We consider two cases: (1) every sibling in a group receives the same random $\omega$ (Uniform Siblings), and (2) every sibling in a group not necessarily receiving the same $\omega$  (Random Siblings). We did this for every tree in Table \ref{tab:five_trees}, with 1000 randomly generated matrices from each tree. The entries of the matrices were generated using a uniform distribution over the interval $[-5,\,5]$. The average spectral radii of the $P$ matrix is recorded in Figure \textbf{Figure}. \textbf{Discussion}

\subsection{Example 2} Second, we randomly generate 100 random trees with 3-10 nodes. On each tree, 1000 random matrices are generated, just as in Example 1. Then, the average spectral radius of each numerical experiment is recorded for each method of determining $\omega$ as in experiment 1 (Unifrom Siblings, Random Siblings, and Kaczmarz with uniform $\omega = 1$). The results can be seen in Figure \textbf{Figure}. \textbf{Discussion}.

\subsection{Example 3} Thirdly, we compare leaf groupings on binary trees. We used binary trees with nodes of 5-80. We ran two experiments on each tree: (1) assigning a uniform $\omega = 1$ to each group and (2) assigning $\omega = 0.75\omega_{max}$ to each group. Both of these experiments were compared to the path graph as well. The linear systems were randomly generated in the same fashion as the other examples. Results are recorded in Figure \textbf{Figure}. \textbf{Discussion}

\end{comment}

config: arxiv


TITLE: Prove: $a_n \leq b_n \implies \limsup a_n \leq \limsup b_n$
QUESTION [3 upvotes]: Is my proof correct? Prove: $a_n \leq b_n \implies \limsup a_n \leq \limsup b_n$
Proof:
Let $a_n$ and $b_n$ be sequences such that $a_n \leq b_n \forall_n$. Suppose $\limsup a_n \nleq \limsup b_n$.
That is: $\limsup a_n > \limsup b_n$. From this we know:
$\forall_{\epsilon > 0} \exists_N \forall_{n>N} \implies |b_n - b| <\epsilon$. Where $b$ is the $\limsup b_n$.
$\forall_{\epsilon_1 > 0} \exists_{N_1} \forall_{n > N_1} \implies |a_n - a| < \epsilon_1$. Where $a$ is the $\limsup a_n$
So, let $a^* = a + \dfrac{\epsilon_1}{2}$ and let $b^* = b - \dfrac{\epsilon}{2}$.
Hence, $a^* \in |a_n - a| <\epsilon_1$ and $b^* \in |b_n - b| < \epsilon$. And clearly we see that $b^* < a^*$.Thus, we have found an element of $b_n$ namely $b^* < a^*$ an element of $a$. This is contradiction since we are given $a_n \leq b_n \forall_n$.
Therefore, the supposition is false, and $\limsup a_n \leq \limsup b_n$.

REPLY [4 votes]: Recall that given a bounded sequence, we define $\limsup a_n$ as
$$\lim a_n^+$$ where
$$a_n^+=\sup\{a_n,a_{n+1},\dots,\}$$
Now, if $a_n\leq b_n$ for each $n$, what can you say about the relaton among each of the values:
$$a_n^+=\sup\{a_n,a_{n+1},\dots,\}$$
$$b_n^+=\sup\{b_n,b_{n+1},\dots,\}$$
What can you then say about their limits?


TITLE: Figuring out values for a tangent equation on a curve
QUESTION [0 upvotes]: "What value of $b$ and $c$ for the curve $y = x^3 + bx^2 + cx$ give the tangent equation $y = 3x - 4$ in the point $(1, -1)$?"
This is what I do:
The derivative of the function is $3x^2 + 2bx + c$
In the point where $x = 1$, it becomes $3 + 2b + c$. Since the tangent equation is $3x - 4$, $3 + 2b + c = 3$. This means that $2b = -c$.
The answer in the book says that $c = -4$, and $b = 2$. However, shouldn't any value that conforms to $2b = -c$ work? I mean, they all give the slope of 3.

REPLY [0 votes]: The question asks you to verify the equation of a tangent line to a given curve at a given point. That point must lie on the curve! You need $x=1$ and $y=-1$ to be a solution to the equation $y=x^3+bx^2+c$, i.e. you need $-1=1+b+c$ or equivalently: $b+c=-2$.
You can then do what you did and find the derivative and get the condition that $2b=-c$.
Solving the equation $b+c=-2$ and $2b=-c$ simultaneously gives $b=2$ and $c=-4$ as the book says.


TITLE: The Mean of a multivariate function
QUESTION [0 upvotes]: Jane and Jack each toss a fair coin twice.
Let X be the number of heads Jane obtains.
Let Y be ther number of heads Jack obtains.
Define U = X + Y.
Find the mean and variance of U.
I have tried to first find f(U) and am unable to.
Would it be:
$$ {4 \choose u}(0.5)^{u}(0.5)^{4-u}  $$
Thank you!

REPLY [1 votes]: Your $P(U=u)$ is correct. Here is a hint, but I encourage you to do the problem your way too, it would be an instructive exercise.
Hint:
$E(X+Y)=E(X)+E(Y)$
If $X$ and $Y$ are independent then $Var(X+Y)=Var(X)+Var(Y)$


text:
\begin{document}
\maketitle

\begin{abstract}
We give  results characterising ternary Kloosterman sums modulo $9$ and $27$. This leads to a complete characterisation of values that ternary Kloosterman sums assume modulo $18$ and $54$. The proofs uses Stickelberger's theorem, the Gross-Koblitz formula and Fourier analysis.
\bigskip

{\bf Keywords:} Kloosterman sums, Stickelberger's theorem, Gross-Koblitz formula
\end{abstract}

\section{Introduction}
Let $\mathcal{K}_{p^n}(a)$ denote the $p$-ary Kloosterman sum defined by
\[
\mathcal{K}_{p^n}(a) := \sum_{x \in \f{p^n}} \zeta^{\Tr (x^{p^n-2}+ax)},
\]
for any $a \in \f{p^n}$, where $\zeta$ is a primitive $p$-th root of unity
and $\Tr$ denotes the absolute trace map $\Tr : \f{p^n} \to \f{p}$ defined as usual as
\[
\Tr (c) := c + c^p + c^{p^2} + \cdots + c^{p^{n-1}}.
\]

Kloosterman sums have
attracted attention thanks to their various links to other related fields. For instance,
a zero of a binary Kloosterman sum on $\f{2^n}$ leads to a bent function from $\f{2^{2n}} \to \f{2}$ as proven by Dillon in \cite{Dil74}. Similarly, zeros of ternary Kloosterman sums give rise to ternary bent functions \cite{HK}. However determining a zero of a Kloosterman sum is not easy. A recent result in this direction is the following: a binary or ternary Kloosterman sum $\mathcal{K}_{p^n} (a)$ is not zero if $a$ is in a proper subfield of $\f{p^n}$
except when $p = 2, n = 4, a = 1$, see \cite{Lisonek2009}.

Given the difficulty of the problem of finding zeros (or explicit values) of Kloosterman sums,
and that they sometimes do not exist,
one is generally satisfied with  divisibility results and characterisation of Kloosterman sums modulo some integer (see \cite{MMeven, LisonekSeta, Div3, CHZ, Lisonek2009}).

It is easy to see that binary Kloosterman sums are divisible by $4 = 2^2$, i.e.,

for all $a \in \f{2^n}$,
\begin{equation}\label{folklore}
\mathcal{K}_{2^n}(a) \equiv 0 \pmod{4}.
\end{equation}

They also satisfy (see \cite{LachWolf})
\[
-2^{n/2+1} \le \mathcal{K}_{2^n}(a) \le 2^{n/2+1},
\]
and take every value which is congruent to $0$ modulo $4$ in that range.

Helleseth and Zinoviev proved the following result which improved \eqref{folklore}
one level higher, i.e., modulo $2^3$,  in the sense
of describing the $a$ for which $\mathcal{K}_{2^n}(a)$ is 0 or 4 modulo 8.

\bigskip

\begin{thm}\cite{HZ}\label{mod8}
For $a \in \f{2^n}$,
\[
\mathcal{K}_{2^n}(a) \equiv \left\{ \begin{array}{ll}
0 \ (\mathrm{mod} \ 8) & \textrm{if } \Tr(a) = 0,\\
4 \ (\mathrm{mod} \ 8) & \textrm{if } \Tr(a) = 1.
\end{array}
\right.
\]
\end{thm}

Similar to the binary case, it is easy to see that ternary Kloosterman sums are divisible by $3$, i.e., for all $a \in \f{3^n}$,
\begin{equation}\label{folklore2}
\mathcal{K}_{3^n}(a) \equiv 0 \pmod{3}.
\end{equation}

Ternary Kloosterman sums satisfy (see Katz and Livn\'e  \cite{Katz})
\[
-2\sqrt{3^n} < \mathcal{K}_{3^n}(a) < 2\sqrt{3^n}
\]
and take every value which is congruent to $0$ modulo $3$ in that range.

We will prove the following theorem, a simple characterisation of ternary Kloosterman sums modulo $3^2$ using the trace map (similar to Helleseth-Zinoviev result for binary case), by using Stickelberger's theorem.

\bigskip

\begin{thm}
For $a \in \f{3^n}$,
\[
\mathcal{K}_{3^n}(a) \equiv \left\{ \begin{array}{ll}
0 \ (\mathrm{mod} \ 9) & \textrm{if } \Tr(a) = 0,\\
3 \ (\mathrm{mod} \ 9) & \textrm{if } \Tr(a) = 1,\\
6 \ (\mathrm{mod} \ 9) & \textrm{if } \Tr(a) = 2.
\end{array}
\right.
\]
\end{thm}

This result is implied by a result of van der Geer and van der Vlugt \cite{Geer}.

We will also give a characterisation modulo $3^3$ of Kloosterman sums, using the Gross-Koblitz formula. The characterisation will depend on a generalisation of the trace function. Note that the trace of an element $a \in \f{q}$ can be written as
\[
\Tr(a) := \sum_{i \in W_1} a^i,
\]

where $W_1 := \{ p^i \ | \ i \in \{0,\ldots,n-1\} \}$. We will use a generalised trace $\tau_S : \f{p^n} \to \f{p}$,
\[
\tau_S(a) := \sum_{i \in S} a^i,
\]
where $S$ can be assigned to any subset of $\{0,\ldots,p^n-2\}$ satisfying
\[
S^p := \{s^p \pmod{p^n-1} \ | \ s \in S\} = S,
\]
particularly quadratic and cubic powers of $p$, in contrast to the set of linear powers $W_1$.

We will define the sets
\begin{align*}
X&:=\{r \in \{0,\dots,q-2\}|r = 3^i+3^j\},\ (i, j \text{ not necessarily distinct})\\
Y&:=\{r \in \{0,\dots,q-2\}|r = 3^i+3^j+3^k, i,j,k \text{ distinct}\},\\
Z&:=\{r \in \{0,\dots,q-2\}|r = 2\cdot3^i+3^j, i\ne j\}.
\end{align*}

Our main result is
\begin{thm}
Let $n\ge 3$, and let $q=3^n$. Then
\begin{equation*}
\K_q(a)\equiv \left\{
	\begin{array}{rcccccl}
		0\pmod{27}\text{ if } &\Tr(a) = &0 &\text{ and } &\tau_{Y}(a) &+2\tau_{X}(a)&=0\\
		3\pmod{27}\text{ if } &\Tr(a) = &1 &\text{ and } &\tau_{Y}(a) & &= 2\\
		6\pmod{27}\text{ if } &\Tr(a) = &2 &\text{ and } &\tau_{Y}(a)&+\tau_{X}(a) &= 2\\
		9\pmod{27}\text{ if } &\Tr(a) = &0 &\text{ and } & \tau_{Y}(a)&+2\tau_{X}(a) &= 1\\
		12\pmod{27}\text{ if } &\Tr(a) = &1 &\text{ and } & \tau_{Y}(a)& &= 0\\
		15\pmod{27}\text{ if } &\Tr(a) = &2 &\text{ and } &\tau_{Y}(a)&+\tau_{X}(a) &= 0\\
		18\pmod{27}\text{ if } &\Tr(a) = &0 &\text{ and } &\tau_{Y}(a)&+2\tau_{X}(a) &=2\\
		21\pmod{27}\text{ if } &\Tr(a) = &1 &\text{ and } &\tau_{Y}(a)& &= 1\\
		24\pmod{27}\text{ if } &\Tr(a) = &2 &\text{ and } &\tau_{Y}(a)&+\tau_{X}(a) &= 1.
		\end{array} \right.
\end{equation*}

\end{thm}

Recently, we have proved a similar result for the binary case, using $\tau_{Q}$, where $Q := \{2^i + 2^j \ | \ i,j \in \{0,\ldots,n-1\}, i \ne j \}$.
\bigskip

\begin{thm}\cite{arxivbinary}
For $a \in \f{2^n}$,
\begin{equation*}
\mathcal{K}_{2^n}(a)\equiv \left\{
	\begin{array}{rccl}
			0 \pmod{16}& \text{ if } &\Tr(a) = 0 \text{ and } &\tau_{Q}(a) = 0,\\
			4\pmod{16}& \text{ if } &\Tr(a) = 1 \text{ and } &\tau_{Q}(a) = 1,\\
			8\pmod{16}& \text{ if } &\Tr(a) = 0 \text{ and } &\tau_{Q}(a) = 1,\\
			12\pmod{16}& \text{ if } &\Tr(a) = 1 \text{ and } &\tau_{Q}(a) = 0.
		\end{array} \right.
		\end{equation*}
\end{thm}

For the ternary case we mention a recent result due to Lisonek \cite{LisonekSeta} that gives a description of the elements $a \in \f{3^n}$ for which $\mathcal{K}(a) \equiv 0 \pmod{9}$, which is also implied by the van der Geer-van der Vlugt result.
\bigskip

\begin{thm}\cite{LisonekSeta}
Let $n \ge 2$. For any $a \in \f{3^n}, \mathcal{K}_{3^n}(a)$ is divisible by $9$ if and only if $\Tr(a) = 0$.
\end{thm}

In Sections \ref{sect::Stickelberger} and \ref{sect::Fourier}, we will introduce the techniques we use. In Section \ref{results} we will give the results modulo $9$. In Section \ref{GKmod27} we will give the modulo $27$ result.

\section{Stickelberger's theorem}\label{sect::Stickelberger}

Let $p$ be a prime (in Section \ref{results} we set $p=3$).
Consider multiplicative characters taking their values in an algebraic extension of $\mathbb
{Q}_p$. Let $\xi$ be a primitive $(q-1)^{\text{th}}$ root of unity in a
fixed algebraic closure of  $\mathbb{Q}_p$.
The group of multiplicative characters of $\mathbb{F}_q$ (denoted $
\widehat{\mathbb{F}_q^{\times}}$) is cyclic of order $q-1$.
The group $\widehat{\mathbb{F}_q^
{\times}}$ is generated by the Teichm\"uller character $\omega : \mathbb{F}_q \to
\mathbb{Q}_p(\xi)$, which, for a fixed generator $t$ of $\mathbb{F}_q^{\times}$, is defined
by $\omega (t^j) = \xi^j$. We set $\omega (0)$ to be $0$. An equivalent definition is that $\omega$ satisfies \[\omega(a) \equiv a \pmod{p}\] for all $a \in \f{q}$.

Let $\zeta$ be a fixed primitive $p$-th root of unity in the
fixed algebraic closure of  $\mathbb{Q}_p$.
Let $\mu$ be the canonical additive character of $\mathbb{F}_q$, \[\mu(x) = \zeta^{\Tr (x)}
\]
where $\Tr$ denotes the absolute trace map from  $\mathbb{F}_q$ to  $\mathbb{F}_p$.

The Gauss sum (see \cite{LN,Wash}) of a character $\chi \in \widehat{\mathbb{F}_q^
{\times}}$  is defined as \[\tau(\chi) = -\sum_{x \in \mathbb{F}_q}\chi(x)\mu(x)\,.\]
We define \[g(j):=\tau(\omega^{-j})\,.\]

For any positive integer $j$, let $\wt_p(j)$ denote the $p$-weight of $j$, i.e.,
\[ \wt_p(j)=\sum_i j_i
\]
where $\sum_i j_ip^i$ is the $p$-ary
expansion of $j$.

Let $\pi$ be the unique ($p-1$)th root of $-p$ in $\mathbb{Q}_p(\xi,\zeta)$ satisfying \[\pi \equiv \zeta - 1 \pmod{\pi^{2}}\,.\]
Wan \cite{Wan}
noted that the following improved version of Stickelberger's theorem is a direct consequence of the Gross-Koblitz formula (see Section \ref{GKmod27}).
\bigskip

\begin{thm}\cite{Wan}\label{Stick+}
Let $1 \le j < q-1$ and let $j =j_0+j_1p+\dots + j_{n-1}p^{n-1}$. Then
\[g(j) \equiv \frac{\pi^{\wt_p(j)}}{j_{0}!\cdots j_{n-1}!} \pmod{\pi^{\wt_p(j)+p-1}}\,.\]
\end{thm}

Stickelberger's theorem, as usually stated,  is the same congruence modulo $\pi^{\wt_p(j)+1}$.

We have (see \cite{GK}) that
$(\pi)$ is the unique prime ideal of $\mathbb{Q}_{p}(\zeta, \xi)$ lying above $p$.
Since $\mathbb{Q}_{p}(\zeta, \xi)$ is an unramified extension of $\mathbb{Q}_{p}(\zeta)$,
a totally ramified (degree $p-1$) extension of $\mathbb{Q}_{p}$, it follows that $(\pi)^{p-1} = (p)$
and $\nu_p(\pi) = \frac{1}{p-1}$.
Here $\nu_p$ denotes the $p$-adic valuation.

Therefore Theorem \ref{Stick+} implies that
$\nu_{\pi}(g(j)) = \wt_p(j)$, and because
$\nu_{p}(g(j)) =\nu_{\pi}(g(j)) \cdot \nu_p (\pi)$ we get
\begin{equation}\label{val}
\nu_p(g(j)) = \frac{\wt_p(j)}{p-1}\,.\end{equation}

In this paper we have $p=3$.  In that case, $\pi=-2\zeta-1$ and $\pi^2 = -3$. Hence \eqref{val} becomes
 \begin{equation}\label{val3}
\nu_3(g(j)) = \frac{\wt_3(j)}{2}\,.\end{equation}

\section{Fourier coefficients}\label{sect::Fourier}

The Fourier transform of a function $f:\mathbb{F}_q \to \mathbb{C}$ at $a \in \mathbb{F}_q$
is defined to be
\[\tfr{f}(a) = \sum_{x \in \mathbb{F}_q} f(x)\mu(ax)\,.\]
The complex number $\tfr{f}(a) $ is called the Fourier coefficient of $f$ at $a$.

Consider monomial functions defined by $f(x) = \mu(x^d)$.
When $d=-1$ we have $\tfr{f}(a) = \mathcal{K}_{p^n}(a)$.
By a similar
Fourier analysis argument to that in Katz \cite{KatzGaussSums} or
Langevin-Leander \cite{LL}, for any $d$ we have
\[
\tfr{f}(a) =\frac{q}{q-1}+ \frac{1}{q-1} \sum_{j=1}^{q-2}\tau(\bar{\omega}^j)\ \tau
(\omega^{jd})\ \bar{\omega}^{jd}(a)
\]
and hence
\[
\tfr{f}(a) \equiv - \sum_{j=1}^{q-2}\tau(\bar{\omega}^j)\ \tau
(\omega^{jd})\ \bar{\omega}^{jd}(a) \pmod{q}\,.
\]
We will use this to obtain congruence information about  Kloosterman sums.
Putting $d=-1=p^n-2$, the previous congruence becomes

\begin{equation}\label{firstKL}
\mathcal{K}(a) \equiv - \sum_{j=1}^{q-2}(g(j))^2\ \omega^{j}(a) \pmod{q}.
\end{equation}
In this paper, $p=3$.
Equation (\ref{val3}) gives the $3$-adic valuation of the Gauss sums $g(j)$,
and the $3$-adic valuation of each term in  equation (\ref{firstKL}) follows.
Our proofs will consider (\ref{firstKL}) at various levels, i.e., modulo $3^2$ and $3^3$.

\section{Ternary Kloosterman sums modulo 9}\label{results}

In this section we will prove our result using Stickelberger's theorem. First we need a lemma which helps us in our proof.

\begin{lem}\label{SumInv}
Let $p$ be a prime, $q = p^n$ and $r \in \mathbb{F}_p^{\times}$. If $T_r$ denotes the set $\{a \in \mathbb{F}_q \mid \Tr (a) = r\}$, then \[\sum_{t \in T_r} t^{-1} = r^{-1}\,.\]
\end{lem}

\begin{proof}

Consider the polynomials \[g(x)= \prod_{t \in T_r}(x-t) \,,\]\[h(x)= \prod_{t \in
T_r}(x-t^{-1}) \,.\]

Note that $g(x)$ vanishes on the $p^{n-1}$ elements of $T_r$. Thus
\[
g(x) = x^{p^{n-1}}+x^{p^{n-2}}+\dots+x-r.
\]
In particular, $$\prod_{t \in T_r}(-t) = -r,$$ so $$\prod_{t \in T_r}(-t^{-1}) = -r^{-1}.$$

The reciprocal polynomial of $g$ is $g^{*}(x) = x^{p^{n-1}}g(1/x)$.

We therefore get
\begin{align*}
h(x) & = -r^{-1}g^{*}(x) \\
		 & = -r^{-1}x^{p^{n-1}}g(1/x)\\
     & = x^{p^{n-1}}-r^{-1}x^{p^{n-1}-1}-\dots-r^{-1}x^{p^{n-1}-p^{n-2}}-r^{-1}\,.
\end{align*}
Thus \[\sum_{t \in T_r}(-t^{-1})=-r^{-1}\,.\]\qedhere

\end{proof}

From now on, we set $p = 3$, so that $\mathcal{K}_q (a)$ is an integer for $a \in \f{q}$. Since there will not be any confusion with binary Kloosterman sums we will write $\mathcal{K}(a)$ for $\mathcal{K}_q(a)$. We consider the function $f(x) = \mu(x^{-1}) = \mu(x^{q-2})$. Then $\tfr{f}(a)$ is the Kloosterman sum $\mathcal{K}(a)$. The following lemma will be needed.

\begin{lem}\label{cong3}
Let $q = 3^n$, and $T_1$ be as defined above. Then
\[\sum_{z\in T_1}\bar{\omega}(z) \equiv 1 \pmod{3}.\]
\end{lem}
\begin{proof}
Follows directly from Lemma \ref{SumInv} and the definition of the Teichm\"uller character.\qedhere
\end{proof}

We can now state our main result of this section.
\bigskip

\begin{thm}\label{mainthmfull}
Let $q=3^n$ for some integer $n>1$.
For $a \in \mathbb{F}_q$,
\begin{equation*}
\mathcal{K}_q(a)\equiv \left\{
	\begin{array}{ll}
			0 \pmod{9} & \text{if } \Tr (a) = 0,\\
			3 \pmod{9} & \text{if } \Tr (a) = 1,\\
			6 \pmod{9} & \text{if } \Tr (a) = 2.
		\end{array} \right.
\end{equation*}
\end{thm}

\begin{proof}
 By \eqref{firstKL}
\begin{equation}
\mathcal{K}(a) \equiv - \sum_{j=1}^{q-2}g(j)^2\ \omega^{j}(a)\pmod{q}\,.\label{Kmodq}
\end{equation}

Let, for any $0 < t < q-1$, the $3$-adic expansion of $t$ be $t = t_{0}+3t_{1}+\dots+3^{n-1} t_{n-1}$ and let $\mathcal{P}$ be the prime of $\mathbb{Q}_3(\xi,\zeta)$ lying above $3$.
As we mentioned in Section 2, Stickelberger's theorem implies that
\begin{eqnarray}
\nu_{\mathcal{P}}(g(t)) & = & \wt_3(t)=t_{0}+t_{1}+\dots+t_{n-1} \nonumber\\
\nu_3(g(t)) & = & \frac{\wt_3(t)}{2}, \nonumber\\
\textrm{and so}\ \nu_3((g(t))^2) & = & \wt_3(t).\label{wt}
\end{eqnarray}
Now (\ref{wt}) implies that any term in the sum in \eqref{Kmodq} with
$\wt_3(j)>1$ will be 0 modulo 9, so \eqref{Kmodq} modulo 9 becomes
a sum over terms of weight 1 only:
\begin{equation*}
\mathcal{K}(a) \equiv - \sum_{0\leq i<n}g(3^i)^2\ \omega^{3^i}(a) \pmod{9}\,.
\end{equation*}
By Lemma 6.5 of \cite{Wash}, $g(3^i) = g(1)$, so we obtain
\begin{equation}\label{ka1}
\mathcal{K}(a) \equiv - g(1)^2\ \sum_{0\leq i<n}\omega^{3^i}(a)\pmod{9}\,.
\end{equation}
By  definition of $\omega$, we have
\begin{equation}\label{ka2}
\sum_{0\leq i<n}\omega^{3^i}(a) \equiv \Tr (a) \pmod{3}\,.
\end{equation}
Since $\nu_3(g(1)^2) =\wt_3(1)=1$,
the proof of the theorem reduces to determining $g(1)^2\  \bmod{9}$.
We calculate, using the notation of Lemma \ref{SumInv},
\begin{align*}
g(1)& = -\sum_{x\in \mathbb{F}_q^{\times}}\bar{\omega}(x)\zeta^{\Tr (x)}\\
&=-\sum_{x\in T_0}\bar{\omega}(x) -\sum_{x\in T_1}\bar{\omega}(x)\zeta -\sum_{x\in
T_1}\bar{\omega}(-x)\zeta^2\\
&=(\zeta^2-\zeta)\sum_{x\in T_1}\bar{\omega}(x)
\end{align*}
because $\bar{\omega}(-x)=-\bar{\omega}(x)$, $T_2=-T_1$,  and
the sum over $T_0$ is 0.
This implies
\[
 g(1)^2 = (\zeta^2-\zeta)^2\left(\sum_{x\in T_1}\bar{\omega}(x)\right)^2.
\]
But we have $(\zeta^2-\zeta)^2 = -3$. This, together with Lemma \ref{cong3}, implies
\begin{equation}\label{6mod9}
g(1)^2 \equiv 6 \pmod{9}.
\end{equation}
Combining this with (\ref{ka2}), the congruence (\ref{ka1}) becomes
\begin{equation*}
\mathcal{K}(a) \equiv 3\ \Tr (a)\pmod{9}
\end{equation*}
as required.
  \qedhere
\end{proof}

Garaschuk and Lisonek proves the following theorem which characterises ternary Kloosterman sums modulo $2$.

\begin{thm}\label{mod2} \cite{Lisonek2009}
Let $\sqrt{a}$ denote any $b \in \f{3^n}$ such that $b^2=a$.
\[
\mathcal{K}_{3^n}(a) \equiv \left\{ \begin{array}{ll}
0 \ (\mathrm{mod} \ 2) & \textrm{if } a = 0 \textrm{ or } a \textrm{ is a square and } \Tr(\sqrt{a}) \ne 0,\\
1 \ (\mathrm{mod} \ 2) & \textrm{otherwise.}
\end{array}
\right.
\]
\end{thm}

Theorem \ref{mainthmfull} and Theorem \ref{mod2} together give a full characterisation of ternary Kloosterman sums modulo $18$, which we summarise in the following corollary.

\begin{cor}\label{mod18}
Let $q=3^n$. For $a \in \mathbb{F}_q^\times$,
\begin{equation*}
\mathcal{K}_q(a)\equiv \left\{
	\begin{array}{rcccccl}
			0  \pmod{18} &\textit{ if } &\Tr(a) = 0 & \textit{and }  a & \textsf{square}      & \textit{with} &\Tr(\sqrt{a}) \ne 0,\\
			3  \pmod{18} &\textit{ if } &\Tr(a) = 1 & \textit{and }  a & \textsf{non-square}  & \textit{or}   &\Tr(\sqrt{a}) = 0, \\
			6  \pmod{18} &\textit{ if } &\Tr(a) = 2 & \textit{and }  a & \textsf{square}      & \textit{with} &\Tr(\sqrt{a}) \ne 0,\\
			9  \pmod{18} &\textit{ if } &\Tr(a) = 0 & \textit{and }  a & \textsf{non-square}  & \textit{or}   &\Tr(\sqrt{a}) = 0,  \\
			12 \pmod{18} &\textit{ if } &\Tr(a) = 1 & \textit{and }  a & \textsf{square}      & \textit{with} &\Tr(\sqrt{a}) \ne 0,\\
			15 \pmod{18} &\textit{ if } &\Tr(a) = 2 & \textit{and }  a & \textsf{non-square}  & \textit{or}   &\Tr(\sqrt{a}) = 0.
		\end{array} \right.
\end{equation*}
\end{cor}

\section{Ternary Kloosterman sums modulo 27}\label{GKmod27}

To be able to give higher level congruences we will need a result stronger than Stickelberger's
theorem.   Recall that Gauss sums lie in $\mathbb{Z}_{p}[\zeta, \xi]$,
and that $(\pi)$ is the unique prime ideal of $\mathbb{Z}_{p}[\zeta, \xi]$ lying above $p$.
All congruences involving Gauss sums take place in this ring, so when we write
$g(j)^2 \equiv 6 \pmod{27}$ we mean that $g(j)^2-6$ is in the ideal $(27)$.
The {\bf Gross-Koblitz formula} \cite{GK,Rob} states that
\begin{equation}\label{GKformula}
g(j) = \pi^{\wt_p(j)}\prod_{i=0}^{n-1}\Gamma_{p}\left(\left\langle \frac{p^{i}j}{q-1} \right\rangle\right)
\end{equation}
where $\langle x \rangle$ is the fractional part of a rational number $x$, and $\Gamma_p$ is the $p$-adic Gamma function $\Gamma_{p}:\mathbb{N} \to \mathbb{N}$ defined by (cf. \cite{Morita})

\[
\Gamma_{p}(k) = (-1)^k\prod_{\substack{t<k\\(t,p) = 1}}t \,.
\]

The following result helps one computing the $p$-adic Gamma function modulo $p^k$.

\begin{thm}[Generalised Wilson's theorem]\cite{Morita}

Suppose $x \equiv y \pmod{p^k}$. If $p^k \ne 4$, then
\[
\Gamma_{p}(x) \equiv \Gamma_p(y) \pmod{p^k}.
\]
\end{thm}

This theorem is actually a consequence of Gauss' generalisation of Wilson's theorem. Now let us prove a lemma on evaluations of the $p$-adic Gamma function. This lemma will allow us to
evaluate Gauss sums for higher moduli and find Kloosterman congruences modulo $27$.
\bigskip

\begin{lem}\label{gammamod}Let $q=3^n$ and let $i$ be an integer in the range $[0,n-1]$. Then
\[
\Gamma_3\left(\left\langle \frac{3^{i}}{q-1} \right\rangle\right) \equiv
\left\{ \begin{array}{ll}
13 \pmod{27} & \textrm{if } i = 1, \\
1 \pmod{27} & \textrm{if } i > 1.
\end{array} \right.
\]
\end{lem}

\begin{proof}
For any $j$, we have $3^j \le q$, and
\[
\left\langle\frac{3^i}{q-1}\right\rangle = \frac{3^i}{q-1} \equiv 3^i(3^j-1) \pmod{3^j},\] so
\[
\Gamma_3\left(\left\langle \frac{3^{i}}{q-1} \right\rangle\right) \equiv \Gamma_3(26\cdot3^i) \pmod{27}.\]
If $i \ge 3$, then $26\cdot 3^i \equiv 0 \pmod{27}$, and
\[
\Gamma_3\left(\left\langle \frac{3^{i}}{q-1} \right\rangle\right) \equiv 1 \pmod{27}\,,
\]

Now $\Gamma_3(26\cdot3) \equiv \Gamma_3(24) \pmod{27}$ using Generalised Wilson's theorem. And $\Gamma_3(24) \equiv 13 \pmod{9}$. Similarly:
\begin{eqnarray*}
\Gamma_3(26\cdot9) & \equiv & 1 \pmod{27}.
\end{eqnarray*}
\end{proof}

Lemma \ref{gammamod} allows us to compute Gauss sums modulo $27$:
\bigskip

\begin{lem}\label{wt1lem}
Let $q=3^n$. Then
\[
g(j)^2 \equiv \left\{ \begin{array}{ll}
6 \pmod{27} & \textrm{if } \wt_p(j) =  1, \\
9 \pmod{27} & \textrm{if } \wt_p(j) =  2, \\
0 \pmod{27} & \textrm{if } \wt_p(j) \ge 3.
\end{array} \right.
\]
\end{lem}

\begin{proof}
Suppose $\wt_p(j) = 1$. By the Gross-Koblitz formula and Lemma \ref{gammamod},
\[
g(j) \equiv 13 \pi \pmod{27}.
\]
Let
\[
g(j) = 27A + 13\pi
\]
for some $A\in \mathbb{Z}_{p}[\zeta, \xi]$. Then
\begin{align*}
g(j)^2 & = 27^2 A^2 + 2\cdot 27\cdot 13 A  + 169\pi^{2} \\
			 & \equiv 169\pi^{2} \pmod{27} \\
			 & \equiv 6 \pmod{27}
\end{align*}
since $\pi^2=-3$. Now suppose $\wt_p(j) = 2$. By the Gross-Koblitz formula,
\[
g(j) \equiv -3 \pmod{9}.
\] Thus $g(j) = 9X-3$ for some $X\in \mathbb{Z}_{p}[\zeta, \xi]$,
so \[g(j)^2 = 81X^2-54X+9 \equiv 9 \pmod{27}.\]

It is clear from the Gross-Koblitz formula that if $\wt_p(j)>2$, then
\[
27 | \pi^{2\wt_p(j)} | g(j)^2.
\]
\end{proof}

Consider again the trace function $\Tr : \f{p^n} \to \f{p}$,
\[
\Tr (c) = c + c^p + c^{p^2} + \dots + c^{p^{n-1}}.
\]

We wish to generalise this definition to a larger class of finite field sums, which includes the usual trace function as a special case.
\bigskip

\begin{defn}\label{trace}
Let $p$ be a prime, let $n\ge 1$ be an integer and let $q=p^n$.
For any $S \subseteq \mathbb{Z}/(q-1)\mathbb{Z}$ satisfying $S^p=S$
where
$S^p := \{s^p \ | \ s \in S\}$,
define the $S$-\emph{trace} to be the function $\tau_S:\f{q} \to \f{p}$,
\[\tau_S(c) := \sum_{s\in S} c^s\,.\]
\end{defn}

Let
\begin{align*}
X&:=\{r \in \{0,\dots,q-2\}|r = 3^i+3^j\},\ (i, j \text{ not necessarily distinct})\\
Y&:=\{r \in \{0,\dots,q-2\}|r = 3^i+3^j+3^k, i,j,k \text{ distinct}\},\\
Z&:=\{r \in \{0,\dots,q-2\}|r = 2\cdot3^i+3^j, i\ne j\}.
\end{align*}

Now we are ready to prove our result on Kloosterman sums modulo $27$.
\bigskip

\begin{thm}\label{mod27} Let $\K_q$ be the usual $q$-ary Kloosterman sum,
let
\[\tfr{\Tr}(a)=\sum_{\wt_{3}(i) = 1}\omega^{i}(a), \ \textrm{and let}\ \
\tfr{\tau_{X}}(a) = \sum_{\wt_{3}(j) = 2}\omega^j(a).\] Then

\begin{equation}\label{hateq}
\K_{3^n}(a) \equiv 21\tfr{\Tr}(a)+18\tfr{\tau_{X}}(a) \pmod{27}.
\end{equation}
\end{thm}
\begin{proof}
Using   \eqref{firstKL} and Lemma \ref{wt1lem}, we get
\begin{align*}
\mathcal{K}(a) & \equiv - \sum_{j=1}^{q-2}g(j)^2\ \omega^{j}(a)\pmod{q} \\
		& \equiv - \sum_{\wt_{3}(j)=1}g(j)^2 {\omega}^{j}(a) - \sum_{\wt_{3}(j)=2} g(j)^2 {\omega}^{j}(a) \pmod{27} \\
		& \equiv -6\sum_{\wt_{3}(j)=1}{\omega}^{j}(a) - 9\sum_{\wt_{3}(j)=2}{\omega}^{j}(a) \pmod{27} \\
&\equiv 21\tfr{\Tr}(a)+18\tfr{\tau_{X}}(a) \pmod{27}.\qedhere
 \end{align*}
\end{proof}

It would be preferable to express the above result in terms of operations within $\f{q}$ itself. Note that in (\ref{hateq}) we only need $\tfr{\Tr}(a)$ modulo $9$ and $\tfr{\tau_{X}}(a)$ modulo $3$. We have
\[
\tau_{X} (a) \equiv \tfr{\tau_{X}}(a) \pmod{3}.
\]
We need to find some condition for $\tfr{\Tr}(a)$ modulo $9$ using functions from $\f{q}$ to $\f{p}$. We will do that in the proof of the following corollary.
\bigskip

\begin{cor}\label{fieldsums}
Let $n\ge 3$, and let $q=3^n$. Then
\[\K_q (a) \equiv 21 \Tr(a)^3+18\tau_{Z}(a)+9\tau_{Y}(a)+18\tau_{X}(a) \pmod{27}.\]
\end{cor}
\begin{proof}

First note that $\tfr{Q}(a) \equiv \tau_{X}(a) \pmod{3}$, by the basic property of the Teichm\"uller character.

To determine $\tfr{\Tr}(a) \bmod{9}$, we compute
\begin{align*}
\tfr{\Tr}(a)^3 &= \sum_{i,j,k \in \{0,\dots,n-1\}}\omega(a^{3^i+3^j+3^k})\\
&=\tfr{\Tr}(a)+3\sum_{r\in Z}\omega(a^{r})+6\sum_{r \in Y}\omega(a^{r})\,,
\end{align*}
and note the elementary fact that if $x \equiv y \pmod{m}$, then $x^m \equiv y^m \pmod{m^2}$. This means that $\tfr{\Tr}(a)^3 \bmod{9}$ is given by $\tfr{\Tr}(a) \bmod{3} = \Tr (a)$, i.e. $\tfr{\Tr}(a)^3 \bmod{9} = \Tr(a)^3$.

Since \[\sum_{r\in Z}\omega(a^{r}) \equiv \tau_{Z}(a)\pmod{3}\]and \[\sum_{r \in Y}\omega(a^{r}) \equiv \tau_{Y}(a)\pmod{3}\,,\]we have that

\[\tfr{\Tr}(a) \equiv \Tr(a)^3 - 3\tau_{Z}(a) - 6\tau_{Y}(a)\pmod{9},\]proving the result.
\end{proof}

Note that
\[\Tr(a) \tau_{X}(a) = \Tr(a)+2\tau_{Z}(a)\,.\]
Thus Corollary \ref{fieldsums} can be rewritten as
\begin{equation}\label{final27}
\K_q (a) \equiv 21 \Tr(a)^3+18\Tr(a)+18\tau_{X}(a)+9\Tr(a)\tau_{X}(a)+9\tau_{Y}(a) \pmod{27}.
\end{equation}
The smallest field for which each of the 27 possible values of $(\Tr(a), \tau_{X}(a), \tau_{Y}(a))$ occurs is $\f{3^6}$.
\bigskip

\begin{cor}
Let $n\ge 3$, and let $q=3^n$. Then
\begin{equation*}
\K_q(a)\equiv \left\{
	\begin{array}{rcccccl}
		0\pmod{27}\text{ if } &\Tr(a) = &0 &\text{ and } &\tau_{Y}(a) &+2\tau_{X}(a)&=0\\
		3\pmod{27}\text{ if } &\Tr(a) = &1 &\text{ and } &\tau_{Y}(a) & &= 2\\
		6\pmod{27}\text{ if } &\Tr(a) = &2 &\text{ and } &\tau_{Y}(a)&+\tau_{X}(a) &= 2\\
		9\pmod{27}\text{ if } &\Tr(a) = &0 &\text{ and } & \tau_{Y}(a)&+2\tau_{X}(a) &= 1\\
		12\pmod{27}\text{ if } &\Tr(a) = &1 &\text{ and } & \tau_{Y}(a)& &= 0\\
		15\pmod{27}\text{ if } &\Tr(a) = &2 &\text{ and } &\tau_{Y}(a)&+\tau_{X}(a) &= 0\\
		18\pmod{27}\text{ if } &\Tr(a) = &0 &\text{ and } &\tau_{Y}(a)&+2\tau_{X}(a) &=2\\
		21\pmod{27}\text{ if } &\Tr(a) = &1 &\text{ and } &\tau_{Y}(a)& &= 1\\
		24\pmod{27}\text{ if } &\Tr(a) = &2 &\text{ and } &\tau_{Y}(a)&+\tau_{X}(a) &= 1.
		\end{array} \right.
\end{equation*}

\end{cor}

\begin{proof}
Restatement of equation \ref{final27}.
\end{proof}

The Kloosterman sums modulo $54$ can be given by combining (\ref{fieldsums}) and Theorem \ref{mod2}.

\bibliographystyle{plain}
\bibliography{main}
\end{document}


TITLE: How to calculate the event horizon and the cosmological radius in a metric?
QUESTION [0 upvotes]: From reading about general relativity,  the event horizon and the cosmological radius are the radius when $f(r)=0$, in the metric
$$
ds^{2}=-f(r)dt^{2}+\frac{dr^{2}}{f(r)}+r^{2}d\Omega^{2}
$$
However, how to distinguish between these two quantities and what happens if $f(R)=0$ has only one solution $r=2M$ or when it has two solution $r=2M$ and $r=R$ where $R>2M$.

REPLY [0 votes]: To calculate event horizon...

It is the radius sphere around a black hole through which even light fails to escape
Therefore, light energy$(E)=mc²$
Energy needed to escape
i.e potential energy=$\frac{GMm}{R}$
Therefore, equating $$mc²=\frac{GMm}{R}$$ $$C²=\frac{GM}{R}$$ $$R=\frac{GM}{c^2}$$
Where, $M$ = mass of the black hole notsure if my logic is correct


TITLE: Find the limit or prove it does not exist for the following rational function
QUESTION [1 upvotes]: I have $$\lim_{(x,y) \rightarrow(1,0)} \frac{x^2y^2 + 2x^2 + 4}{xy - x - 2}$$
All linear approaches ( as in, using $y = m(x-1)$ ) converge to $-2$, so I tried to prove this using epsilon-delta definition, but I don't know which inequalities to use at any step

REPLY [3 votes]: You're overcomplicating things a little.
There's no problem with division by zero in this case, so the function (being rational) is continuous at the point $(1,0)$, and therefore you can find the limit simply by substituting $(x,y)=(1,0)$ into the expression.


TITLE: Question about photoelectric effect
QUESTION [0 upvotes]: Let's say we have a metallic plate and a light source so that each atom of the metal will receive $15'6\space \frac{meV}{s}$ (mili electron volts per second). Assuming the work function of the metal is $\Phi=2\space eV$, we can calculate how much time we would need for the photoelectric effect to happen according to classic theory: $$2\space eV=\int_{0}^t15'6·10^{-3}dt<=>t=128\space seconds$$
Now, we actually know there is no delay in the photoelectric effect, so a photon of at least $E=2\space eV$ (assuming our light's wave length is $\lambda=\frac{hc}{2\space eV}=620'8\space nm $) should hit an atom once the light is lit up.
My question is,
how is it possible for an atom to receive $2\space eV$ at an instant if we said that it receives $15'6\space \frac{meV}{s}$?

REPLY [2 votes]: according to classic theory ... how is it possible for an atom to receive 2 eV at an instant

It's not. That's one the reasons the photoelectric effect was considered to be evidence against classical mechanics.
In quantum theory, the 15.6 meV/s is the average across all atoms, not the amount that each atom gets; each atom either gets a whole photon's worth of energy, or none at all.


TITLE: Were Kepler's Laws of Planetary Motion the first formal definition of an ellipse?
QUESTION [1 upvotes]: It seems to me that Kepler's Laws necessitate some definition of an ellipse in terms of a coordinate system. I am wondering whether Kepler's Laws mathematically defined what an ellipse is, or if he used an already defined shape in his laws.
The reason I got curious about this in the first place was that I realized that Descartes may not have invented the Cartesian coordinate system by the time that Kepler discovered these laws and I have only seen proofs of Kepler's Laws in a Cartesian system.

REPLY [9 votes]: Due to the geometric formulation, Kepler's Astronomia Nova is full of elaborate illustrations of ellipses, epicircles and whatnot.  It is not necessary to spell out the position of points in Cartesian coordinates, because the relation between points are specified in angles, lengths, and geometric constructions.
Kepler presents the use of ellipses for planetary motion in Astronomia Nova (1609, originally in Latin; translated by William H. Donahue, 1992, Cambridge University Press), when René Descartes was thirteen years old.  Paging through introductory words by Kepler himself, translators, and commenters (Max Caspar, Kepler, 1993, Dover Publications) is highly recommended because, oh, do they throw shade.
The definition of an ellipse as a conic section, as known to the Greeks, already is a formal definition.  Kepler actually cites the Greek philosophers for many propositions.  For an in depth historical view, see chapter 2.1 of The Ellipse: A Historical and Mathematical Journey by Arthur Mazer (2010, Wiley).


text:
{\bf Problem.} What is the intersection point of the line $y = 2x + 5$ and the line perpendicular to it that passes through the point $(5, 5)$?
{\bf Level.} Level 4
{\bf Type.} Algebra
{\bf Solution.} The slope of $y = 2x + 5$ is 2, which means the slope of any line perpendicular to it is $-\frac 12$.  Using the point-slope equation for a line we can find the equation of the second line to be $y - 5 = -\frac 12 (x - 5)$.  To find the intersection of this with the first line, we plug $y = 2x + 5$ into the second equation to get $2x + 5 - 5 = - \frac 12 (x - 5) \Rightarrow \frac {5}2 x = \frac 52 \Rightarrow x = 1$.  Therefore $y = 2\cdot 1 + 5 = 7$ making the intersection at $\boxed{(1, 7)}$.

set_name: MATH


TITLE: Suppose $(a_n)_{n \geq 0}$ is a decreasing sequence with limit $0$. Prove that $(b_n)$ is a decreasing sequence
QUESTION [3 upvotes]: Suppose $(a_n)_{n \geq 0}$ is a decreasing sequence with limit $0$. Define $$b_n=\frac{\sum_{i=1}^{n}{a_i}}{n}$$ Prove that $(b_n)$ is a decreasing sequence. My attempt is consider $$\frac{b_{n+1}}{b_n}=(\frac{n}{n+1})(\frac{\sum_{i=1}^{n+1}{a_i}}{\sum_{i=1}^{n}{a_i}}) \leq (\frac{\sum_{i=1}^{n+1}{a_i}}{\sum_{i=1}^{n}{a_i}})=1+\frac{a_{n+1}}{\sum_{i=1}^{n}{a_i}}$$ Then i stuck here. I don know how to show $\frac{a_{n+1}}{\sum_{i=1}^{n}{a_i}} \leq 0$ or it is not true itself. Any one can guide me ?

REPLY [5 votes]: $$\begin{align} b_n-b_{n+1} &=\frac{(n+1)\sum_{i\le n}a_i -  n\sum_{i\le n+1} a_i}{n(n+1)} =  \\ &=
\frac{\sum_{i\le n}a_i - na_{n+1}}{n(n+1)} = \frac{\sum_{i\le n}(a_i -a_{n+1})}{n(n+1)} \ge 0  \end{align}$$
where $a_i\ge a_{n+1}$is used for all $i=1,\dots, n$.

REPLY [1 votes]: Indeed you have to show,
$$b_{n}\geq b_{n+1}$$
$$\frac{\sum_{i=1}^{n}{a_i}}{n}\geq \frac{\sum_{i=1}^{n+1}{a_i}}{n+1}$$
$$n\sum_{i=1}^{n}{a_i}+\sum_{i=1}^{n}{a_i}\geq n\sum_{i=1}^{n}{a_i}+na_{n+1}$$
$$\sum_{i=1}^{n}{a_i}\geq na_{n+1}$$
It's clearly true since {$a_i$} is decreasing. You'll over-complicate things to compare in form of a fraction.


TITLE: Prove that $\lim_{n\to\infty} \frac{a^{1/n} - 1}{1/n} = \ln a$
QUESTION [1 upvotes]: Let $a>1$. If someone could give me an extended prove of that result using only sequence sequences, I would really appreciate it.
Thanks in advance.

REPLY [1 votes]: $$\frac{a^{\frac1n} - 1}{\frac1n} = \ln a \frac{e^{\frac{\ln a}{n}} - 1}{\frac{\ln a}{n}} \to \ln a \cdot 1=\ln a$$


TITLE: $\frac{\sigma(n)}{n}=\frac{5}{3}\,\,\,\Rightarrow\,\,\,\,$ $\sigma(5n)=10n$
QUESTION [2 upvotes]: Let $n$ a positive integer so that $$\frac{\sigma(n)}{n}=\frac{5}{3}$$ Show that $5n$ is a perfect number i.e $\sigma(5n)=10n$.
Note: $\sigma(n)$ is the sum of all positive divisors of $n$.

REPLY [5 votes]: It is easy to show that if $n$ and $\sigma(n)$ are both odd, then $n$ is a square; and that $\sigma(n)/n$ is equal to the sum of the reciprocals of the factors of $n$.  From the latter it follows immediately that
$$\hbox{if}\quad m\mid n \quad\hbox{then}\quad
  \frac{\sigma(m)}{m}\le\frac{\sigma(n)}{n}\ .$$
Now suppose that
$$\frac{\sigma(n)}{n}=\frac53\ .\tag{$*$}$$
Since
$$\frac{\sigma(6)}{6}=2>\frac53\quad\hbox{and}\quad
  \frac{\sigma(45)}{45}=\frac{26}{15}>\frac53\ ,$$
neither $6$ nor $45$ is a factor of $n$.  From $(*)$ and the aforementioned results we obtain
$$3\mid n\quad\Rightarrow\quad \hbox{$n$ is odd}\quad\Rightarrow\quad
  \hbox{$n$ is a square}\quad\Rightarrow\quad 3^2\mid n\quad\Rightarrow\quad
  5\not\mid n\ ,$$
and so we can use multiplicativity:
$$\sigma(5n)=\sigma(5)\sigma(n)=6\Bigl(\frac{5n}{3}\Bigr)=10n\ .$$
Thus $5n$ is perfect.
Comment ...and of course $5n$ is odd.  At present, the existence of odd perfect numbers is an unsolved problem ;-)


TITLE: Instead of mid-point, how do i find a third of the way up the line instead.
QUESTION [1 upvotes]: I'm working with the program Maya, and i need to script a way to find various fractions up a line for each 3D vector.
For example, lets say I have the vector (0, 0, 0), and the vector (12, 12, 12).
The midpoint formula would be x1+x2/2, y1+y2/2, z1+z2/2 = (6, 6, 6)
And that's great if I only need the midpoint, but I need to calculate points on a line at different distances.
For example, if I need 2 points, I need to be able to put a point at the 1/3 mark of the line, and the 2/3 mark of the line.
If i have 3 points, i need to put the points on the 1/4, 1/2, and 3/4 of the line.
Dividing this formula by 3 or 4 doesn't work, so is there any formula or expression that will allow me to do something like this? Preferably with one variable to plug in rather than a different way to calculate for every single possibility, or is that not possible.
If not, I may be able to work with the nodes in the program instead to maybe accomplish this, but I would rather solve this problem with pure math instead.

REPLY [1 votes]: Let $A=(a_1,a_2,a_3)$ and $B=(b_1,b_2,b_3)$. The points you are looking for have shape
$$\left((1-t)a_1+tb_1,(1-t)a_2+tb_2 , (1-t)a_3+tb_3\right),$$
where $t$ is a parameter of your choosing.
For the point half-way between $A$ and $B$, we use $t=\frac{1}{2}$. This gives the same result as the formula you mentioned in the post.
For the point $\frac{1}{3}$ of the way from $A$ to $B$, use $t=\frac{1}{3}$.  For the point $\frac{7}{9}$ of the way from $A$ to $B$, use $t=\frac{7}{9}$.
For the three points $\frac{1}{4}$, $\frac{1}{2}$, and $\frac{3}{4}$ of the way from $A$ to $B$, use $t=\frac{1}{4}$, $t=\frac{1}{2}$, and $t=\frac{3}{4}$. And so on.


text:
\section{Modification of known recurrence relations}
\label{sec:known_rec_rel}

There are already several recurrence relations known for the independence polynomial. The most widely used is the standard recurrence relation given above.

\begin{prop}[Proposition 7 in \cite{gutman1983}] \label{prop:rec_rel_sg_v}
Let $G = (V, E)$ be a simple graph and $v \in V$. The independence polynomial satisfies
\begin{align}
I(G, x) = I(G_{\vdel v}) + x \cdot I(G_{\vsdel N_G[v]}).
\end{align}
\end{prop}

In this recurrence relation, the first term counts exactly those independent sets of $G$ not including the vertex $v$, whereas the second term counts exactly those independent sets including the vertex $v$ (and therefore none of its neighbors). This recurrence relation can be generalized to any vertex subset in two different ways as stated in the next two theorems.

\begin{theo}[Theorem 3.7 in \cite{hoede1994}] \label{theo:rec_rel_sg_vs_1}
Let $G = (V, E)$ be a simple graph and $U \subseteq V$ a vertex subset. Then
\begin{align}
& I(G, x) = I(G_{\vsdel U}, x) + \sumsr{\substack{\emptyset \subset W \subseteq U \\ W \text{ is independent in }G}}{(-1)^{\abs{W}+1} \: x^{\abs{W}} \cdot I(G_{\vsdel N_{G}[W]}, x)}.
\end{align}
\end{theo}

In this equality, the summation is over the vertex subsets of $U$ which are at least in the independent sets of $G$. Changing the summation to the vertex subsets exactly in the independent sets of $G$, the expression simplifies.

\begin{theo}[\footnote{In \cite{trinks2013} the present author mentioned a special case of this theorem (as Theorem 2) and misleadingly referred it to the reference of the Theorem \ref{theo:rec_rel_sg_vs_1} above.}] \label{theo:rec_rel_sg_vs}
Let $G = (V, E)$ be a simple graph and $U \subseteq V$ a vertex subset. Then
\begin{align}
& I(G, x) = \sumsr{\substack{W \subseteq U \\ W \text{ is independent in }G}}{x^{\abs{W}} \cdot I(G_{\vsdel U \vsdel N_{G}(W)}, x)}.
\end{align}
\end{theo}

\begin{proof}
We prove the statement by induction on the number of vertices in $U$. As basic step we consider the case $|U| = 1$, say $U = \{u\}$. From the standard recurrence relation (Proposition \ref{prop:rec_rel_sg_v}) we get
\begin{align*}
I(G, x) &= I(G_{\vdel u}, x) + x \cdot I(G_{\vdel u \vsdel N_{G}(u)}, x), \\
&= \sumsr{\substack{W \subseteq U = \{u\} \\ W \text{ is independent in }G}}{I(G_{\vsdel U \vsdel N_{G}(W)}, x)}.
\end{align*}
As induction hypothesis we assume that the statement holds for all sets $U$ with $|U| \leq n$. Let $U' = U \cup \{u\}$ with $\abs{U} = n$. Applying the standard recurrence relation and the induction hypothesis we obtain
\begin{align*}
I(G, x)
&= I(G_{\vdel u}, x) + I(G_{\vdel u \vsdel N_{G}(u)}) \\
&= \sum_{\mathrlap{\substack{W \subseteq U \\ W \text{ is independent in }G_{\vdel u}}}}{I(G_{\vdel u \vsdel U \vsdel N_{G_{\vdel u}}(W)}, x)} + \sum_{\mathrlap{\substack{W \subseteq U \setminus N_{G}(u) \\ W \text{ is independent in }G_{\vdel u \vsdel N_G(u)}}}}{I(G_{\vdel u \vsdel N_{G}(u) \vsdel U \vsdel N_{G_{\vdel u \vsdel N_G(u)}}(W)}, x)} \\
&= \sum_{\mathrlap{\substack{W \subseteq U \\ W \text{ is independent in }G_{\vdel u}}}}{I(G_{\vdel u \vsdel U \vsdel N_{G}(W)}, x)} + \sum_{\mathrlap{\substack{W \subseteq U \setminus N_{G}(u) \\ W \text{ is independent in }G_{\vdel u \vsdel N_G(u)}}}}{I(G_{\vdel u \vsdel N_{G}(u) \vsdel U \vsdel N_{G}(W)}, x)} \\
&= \sum_{\mathrlap{\substack{W' \subseteq U' \\ W' \text{ is independent in }G \\ u \notin W'}}}{I(G_{\vsdel U' \vsdel N_{G}(W')}, x)} + \sum_{\mathrlap{\substack{W' \subseteq U' \\ W' \text{ is independent in} G \\ u \in W'}}}{I(G_{\vsdel U' \vsdel N_{G}(W')}, x)} \\
&= \sum_{\mathrlap{\substack{W' \subseteq U' \\ W' \text{ is independent in }G}}}{I(G_{\vsdel U' \vsdel N_{G}(W')}, x)},
\end{align*}
where the third equality holds because
$G_{\vsdel A \vsdel N_{G_{\vsdel A}}(B)} = G_{\vsdel A \vsdel N_G(B)}$.
Thus, the statement also holds when $|U'| = n+1$, which proves the theorem.
\end{proof}

In the special case were $U$ is a clique, the index of the summation reduces to the vertices of $U$.

\begin{coro}[Corollary 3.8 in \cite{hoede1994}]
Let $G = (V, E)$ be a simple graph and $U \subseteq V$ a vertex subset that induces a complete subgraph. Then
\begin{align}
I(G, x) = I(G_{\vsdel U}, x) + x \cdot \sumsr{u \in U}{I(G_{\vsdel N[v]}, x)}.
\end{align}
\end{coro}

As previously mentioned in the introduction, the standard recurrence relation as given in Proposition \ref{prop:rec_rel_sg_v} is not valid for hypergraphs. For example, observe a hypergraph with three vertices connected by the sole edge. In fact, the standard recurrence relation is not true for graphs with loops, even in the case of a single vertex with a loop.

The reason is that in such situation the second term of the sum, $I(G_{\vsdel N[v]}, x)$, does not count the number of independent sets including $v$ correctly. In the case of a loop incident to $v$, $I(G_{\vsdel N[v]}, x)$ counts too much: At least the empty set is counted as an independent set of $G_{\vsdel N[v]}$, which corresponds to the independent set $\{v\}$ of $G$, but there are no independent sets including $v$. On the other hand, if $v$ is a vertex of a (hyper)edge with more than two vertices, then $I(G_{\vsdel N[v]}, x)$ counts too little: By deleting the neighborhood of $v$, there are also some vertices deleted, that may be in an independent set together with $v$.

Instead of $G_{\vsdel N[v]}$, the hypergraph $G_{\vhid v}$ can be observed to count the number of independent vertex set including $v$. This approach also works for vertex subsets.

\begin{lemm} \label{lemm:independent_sets_including}
Let $G = (V, E)$ be a hypergraph with independent sets $U, \{v\} \subseteq V$. The restricted independence polynomial satisfies
\begin{alignat}{2}
& I_{U \subseteq }(G, x)
&&= x^{\abs{U}} \cdot I(G_{\vshid U}, x), \quad \text{and particularly} \\
& I_{v \in}(G, x)
&&= x \cdot I(G_{\vhid v}, x).
\end{alignat}
\end{lemm}

\begin{proof}
The statement equals the claim that (for an independent set $U$) the independent sets of $G_{\vshid U}$, together with $U$, are exactly the independent sets of $G$ including $U$. Independent sets of a graph are exactly those vertex subsets not including any edge of that graph. Therefore, in each independent set of $G$ including $U$ at least one vertex (not in $U$) of each edge of $G$ is missing. But the same holds for the independent set of $G_{\vshid U}$ joined with $U$, because the edges of $G_{\vshid U}$ are subsets of the edges of $G$ (missing the vertices from $U$).
\end{proof}

Indeed, if there is an edge which is a subset of $W$, then $G_{\vshid W}$ is not defined, as we would end up with an empty edge. We give a further comment about this observation in Section \ref{sec:open_problems}.

\begin{theo} \label{theo:rec_rel_hg_v}
Let $G = (V, E)$ be a hypergraph and $v \in V$. The independence polynomial satisfies
\begin{align}
I(G, x) =
\begin{cases}
I(G_{\vdel v}, x) + x \cdot I(G_{\vhid v}, x) & \text{if } \{v\} \notin E, \\
I(G_{\vdel v}, x) & \text{else.}
\end{cases}
\end{align}
\end{theo}

\begin{proof}
The independent set of $G$ not including $v$ are the independent edges of $G_{\vdel v}$. If there is a loop incident to $v$, i.e.\ $\{v\} \in E$, then there is no independent set in $G$ including $v$. Thus, all independent sets of $G$ are counted by $I(G_{\vdel v}, x)$. Otherwise, if there are no loops incident to $v$, then by Lemma \ref{lemm:independent_sets_including} the independent sets of $G$ including $v$ are exactly those of $G_{\vhid v}$ joined with $\{v\}$.
\end{proof}

Indeed, this theorem is a generalization of the standard recurrence relation in the case of simple graphs: Applying $\vhid v$, loops arise for all neighbors of $v$. Consequently, these vertices can be deleted and we end up with the graph $G_{\vsdel N[v]}$.

Analogous to Theorem \ref{theo:rec_rel_sg_vs} for simple graphs, the theorem above can be generalized to vertex subsets.

\begin{theo} \label{theo:rec_rel_hg_vs}
Let $G = (V, E)$ be a hypergraph and $U \subseteq V$ a vertex subset. The independence polynomial satisfies
\begin{align}
I(G, x) = \sumsr{\substack{W \subseteq U \\ W \text{ is independent in }G}}{x^{\abs{W}} \cdot I(G_{\vshid W \vsdel U}, x)}.
\end{align}
\end{theo}

The proof of this statement is analogously to the case of simple graphs given in Theorem \ref{theo:rec_rel_sg_vs}. While the sum in the previous theorem concerns the vertices exactly in the independent sets, it is quite possible to consider the vertices at least in the independent sets, which gives a statement corresponding to Theorem \ref{theo:rec_rel_sg_vs_1}.

\begin{theo} \label{theo:rec_rel_hg_vs_1}
Let $G = (V, E)$ be a hypergraph and $U \subseteq V$ a vertex subset. The independence polynomial satisfies
\begin{align}
I(G, x) = I(G_{\vsdel U}, x) + \sumsr{\substack{\emptyset \subset W \subseteq U \\ W \text{ is independent in }G}}{(-1)^{\abs{W}+1} \: x^{\abs{W}} \cdot I(G_{\vshid W}, x)}
\end{align}
\end{theo}

\begin{proof}
The independent sets of $G$ not including any vertex of $U$ are enumerated by the first term, $I(G_{\vsdel U}, x)$. Thus, we are left with the enumeration of the independent set including at least one vertex of $U$, which can be calculated via the principle of inclusion-exclusion by $\sum_{\emptyset \subset W \subseteq U}{(-1)^{\abs{W}+1} \cdot I_{W \subseteq}(G, x)}$. Substituting $I_{W \subseteq}(G, x)$ for $x^{\abs{W}} \cdot I(G_{\vshid W}, x)$, following Lemma \ref{lemm:independent_sets_including}, we obtain the second term.
\end{proof}

We present another known recurrence relation for the independence polynomial of simple graphs with respect to an edge deletion.

\begin{prop}[Theorem 3.9 in \cite{hoede1994}] \label{prop:rec_rel_sg_e}
Let $G = (V, E)$ be a simple graph and $e = \{u, v\} \in E$. The independence polynomial satisfies
\begin{align}
I(G, x) = I(G_{-e}, x) - x^2 \cdot I(G_{\vsdel N[e]}, x).
\end{align}
\end{prop}

Therein, the first term counts all independent sets of $G$, but additionally counts such including both vertices of $e$. But those are exactly subtracted by the second term.

As easily seen from the value $x^2$ related to the number of vertices of $e$, this recurrence relation is only valid for simple graphs. However, if there is no other edge that is a subset of the observed edge, the statement can be can be generalized to edges with more than two incident vertices using a similar idea.

\begin{theo} \label{theo:rec_rel_hg_e}
Let $G = (V, E)$ be a hypergraph and $e \in E$ an edge with $\abs{e} > 1$. The independence polynomial satisfies
\begin{align}
I(G, x) =
\begin{cases}
I(G_{-e}, x) - x^{\abs{e}} \cdot I(G_{-e \vshid e}, x) & \text{if } \nexists f \in E \colon f \subseteq e, \\
I(G_{-e}, x) & \text{else.}
\end{cases}
\end{align}
\end{theo}

\begin{proof}
By the first term all independent sets of $G$ are counted, but additionally such independent set including all vertices of $e$.

If there exists an edge $f \in E$ with $f \subseteq e$, then independent set including all vertices of $e$ must also include all vertices of $f$ which contradict the assumption that these are independent sets. Consequently, in this case there are no independent set which are supersets of $e$.

Otherwise, i.e. if there is no such edge $f$, by Lemma \ref{lemm:independent_sets_including} the independent sets including the vertices of $e$ are enumerated by $x^{\abs{e}} \cdot I(G_{-e \vshid e}, x)$.
\end{proof}