TITLE: Let a, b, c be ints. $\frac{ab}{c} + \frac{bc}{a} + \frac{ac}{b}$ is an int, show that each of $\frac{ab}{c}, \frac{bc}{a}, \frac{ac}{b}$ is an int.
QUESTION [3 upvotes]: Let a, b, c $\in \mathbb{Z}$ . If $\frac{ab}{c} + \frac{bc}{a} + \frac{ac}{b}$ is an integer, prove that each of $\frac{ab}{c}, \ \frac{bc}{a}, \ \frac{ac}{b}$ is an integer.
I've tried to solve this problem but still got no solution. All I think is divisibility and GCD
$\frac{ab}{c} + \frac{bc}{a} + \frac{ac}{b} \\ = \frac{a^{2}b^{2} + b^{2}c^{2} + a^{2}c^{2}}{abc}$
Note that $2a^{2}bc + 2ab^{2}c + 2abc^{2}$ is divisible by abc. Put those in, we get:
$\frac{a^{2}b^{2} + b^{2}c^{2} + a^{2}c^{2} + 2a^{2}bc + 2ab^{2}c + 2abc^{2}}{abc} \\ = \frac{(ab + bc + ac)^{2}}{abc}$
Because it's an integer, thus $abc \mid (ab + bc + ac)^{2}$
Assume $GCD(ab + bc + ac, abc) = d$, then $ab + bc + ac = dk_1$ and $abc = dk_2$ for an integer d where $GCD(k_1, k_2) = 1$
$\frac{(ab + bc + ac)^{2}}{abc} = \frac{d^{2}{k_1}^{2}}{dk_2} = \frac{d{k_1}^2}{k_2}$
Because $GCD(k_1, k_2) = 1$, thus the only possibility is $k_2 \mid d$. Let d = $k_{2}p$ where p is an integer, thus it implies that $abc = dk_2 = {k_2}^{2}p$
I got stuck here, I probably used the wrong method to solve this problem, does anyone know how to solve this?

REPLY [1 votes]: You can use divisibility as I show here. First, let
$$\frac{ab}{c} = \frac{d_1}{e_1} \tag{1}\label{eq1A}$$
$$\frac{bc}{a} = \frac{d_2}{e_2} \tag{2}\label{eq2A}$$
$$\frac{ac}{b} = \frac{d_3}{e_3} \tag{3}\label{eq3A}$$
where each fraction $\frac{d_i}{e_i}$ for $1 \le i \le 3$ is in lowest terms, i.e., $\gcd(d_i, e_i) = 1$. Since the sum of these fractions is an integer, say $n$, we have
$$\begin{equation}\begin{aligned}
\frac{d_1}{e_1} + \frac{d_2}{e_2} + \frac{d_3}{e_3} & = n \\
d_1(e_2)(e_3) + d_2(e_1)(e_3) + d_3(e_1)(e_2) & = n(e_1)(e_2)(e_3)
\end{aligned}\end{equation}\tag{4}\label{eq4A}$$
Consider one of the fractions in the first $3$ equations to not be an integer, say WLOG in \eqref{eq1A}, then there exists a prime $p \mid e_1$, so $p \not\mid d_1$. Using the $p$-adic order function, i.e., which gives the highest power of $p$ which divides a given value, we have
$$\nu_p(e_1) \gt 0 \implies \nu_p(c) \gt \nu_p(a) + \nu_p(b) \tag{5}\label{eq5A}$$
If $p \not\mid e_2$ and $p \not\mid e_3$, then in \eqref{eq4A} on the left side, $p$ doesn't divide the first term, but it divides the second & third terms, plus it divides the right side term, which is not possible. Thus, $p \mid e_2$ and/or $p \mid e_3$, say WLOG we have $p \mid e_2$. This gives
$$\nu_p(e_2) \gt 0 \implies \nu_p(a) \gt \nu_p(b) + \nu_p(c) \tag{6}\label{eq6A}$$
Substituting this into \eqref{eq5A} gives
$$\begin{equation}\begin{aligned}
\nu_p(c) & \gt (\nu_p(b) + \nu_p(c)) + \nu_p(b) \\
\nu_p(c) & \gt 2\nu_p(b) + \nu_p(c) \\
0 & \gt 2\nu_p(b)
\end{aligned}\end{equation}\tag{7}\label{eq7A}$$
which is not possible since $\nu_p(b) \ge 0$. Thus, the original assumption that one of the fractions in \eqref{eq1A}, \eqref{eq2A} or \eqref{eq3A} is not an integer must be false, i.e., they are actually all integers instead.


TITLE: Is it possible to express XOR purely in terms of the Sheffer stroke ($↑$)?
QUESTION [1 upvotes]: I've been trying to do it myself but I can only get as far as
$$\begin{align}
P ⊕ Q &= (P \vee Q) \wedge ¬(P \wedge Q) \\
      &= (P \vee Q) \wedge (P ↑ Q) \\
      &= ((P ↑ P) ↑ (Q ↑ Q)) \wedge (P ↑ Q).
\end{align}$$
If it is possible then a pointer in the right direction would be greatly appreciated, if not then is there a way to prove it?

REPLY [0 votes]: Thanks to Rahul's help I was able to derive an expression using just $\uparrow$ equivalent to $A \oplus B$ which is $(A \uparrow (B \uparrow B)) \uparrow ((A \uparrow A) \uparrow B)$


TITLE: How do you solve the summation of $2-4+8-16+32- \dots 2^{48}$?
QUESTION [3 upvotes]: This is a summation problem but I can't seem to figure out how to solve this with the mix of subtraction and addition.

REPLY [3 votes]: No need to use the formula for the geometric series.
$$\begin{align}
S&=2-4+8-16+32- \dots -2^{48}\\
2\,S&=4-8+16-32+\dots+2^{48}-2^{49}
\end{align}$$
Add them and voilà!


TITLE: Linear electric currents
QUESTION [0 upvotes]: If I have a really long conductor (wire for example) as thin as possible, the currents inside are linear by aproximation? I have been thinking about Ampére's law $\int _c \vec B .d \vec {l} = I \mu$, where $c$ is a closed path. The linear current could be expressed as $I_l = \int \vec j . d \vec l$, where $ \vec j$ is a current density.
Is it possible to write just $ \vec B = \vec j \mu$ in this case?
I am somehow confused about the linear, surface and volume currents when they are the source for the magnetic field.

REPLY [0 votes]: The current relates to the current density by a surface integral $$I=\int_A \vec j d\vec a$$ where $A$ is the cross sectional surface of the wire. Thus you cannot equate the contour integral of Ampere's law to the surface integral relating the total current through the wire to the current density and the assumption $$ \vec B = \vec j \mu$$ is wrong.


TITLE: If $q$ is a monic polynomial, then $qf=qg \implies f=g$
QUESTION [1 upvotes]: For a monic polynomial $q\in R[X]$, prove that $qf=qg$ implies $f=g$,
  where $f,g\in R[X]$.

Note: by assumption, rings are commutative.
I don't understand this problem. Can't I just say "perform polynomial division by $q$ on both sides"? Does it not work this way?
Also, if I could show that $R[X]$ is a field, then I could multiply on the left by $q^{-1}$. But $R[X]$ is not necessarily a field. Is there something about $q$ being monic that implies it has a multiplicative inverse?
Thanks!

REPLY [1 votes]: Hint: Basically, you need to prove that $qf=0$ implies $f=0$.
This is not true if $q$ is not monic - specifically, if $q$ has a zero divisor for initial coefficient. Take $R=\mathbb Z/4\mathbb Z$, with $q=f=2X$.


TITLE: Solving $u''-4u=\lambda u$ with Sole Boundary Condition $u'(0)=u(\pi)$
QUESTION [1 upvotes]: Find the eigenfunctions and eigenvalues of the boundary value problem,  $$u''-4u=\lambda u, \ \ \ 0<x<\pi$$ with $u'(0)=u(\pi)$. Check that the resulting eigenfunctions are orthogonal.

I have solved many problems similar to this, but with more than one boundary condition. I don't see how this problem is solved given this single condition.
My attempt:
\begin{align}
u''-u(4+\lambda)&=0 \\
u''-u\mu&=0, \ \ \text{where $\mu=4+\lambda$.} \\
\end{align}
Consider values of $\mu$. If $\mu=0$, then
\begin{align}
u''&=0 \\
u(x)&=Ax+B \ \ \  \ A,B\in\mathbb{R} \\
u(x)&=Ax+A(1-\pi) \ \ \ \text{(using boundary condition)}.
\end{align}
Continuing in this way, I found no trivial solutions for values of $\mu$? How can this be?

REPLY [1 votes]: Clearly if $\mu=0$, the eigenproblem is trivial. For $\mu\neq0$, the corresponding characteristic equation is given
$$ r^2-\mu =0$$
which has two roots $r=\pm\sqrt{\mu}$ if $\mu>0$ or $r=\pm\sqrt{-\mu}i$ if $\mu<0$. Then the general solution of
$$ u''-u\mu=0 $$
is
$$u=Ae^{\sqrt{\mu}x}+Be^{-\sqrt{\mu}x} $$
if $\mu>0$ or
$$u=A\sin(\sqrt{-\mu}x)+B\cos(\sqrt{-\mu}x) $$
if $\mu<0$.
Case 1: $\mu>0$. Using $u'(0)=u(\pi)$, one has
$$ \sqrt{\mu}A-\sqrt{\mu}B=0, Ae^{\sqrt{\mu}\pi}+Be^{-\sqrt{\mu}\pi}=0$$
From this, it is easy to see that $A=B=0$; namely, the problem does not have nonzero eigenfunction.
Case 1: $\mu>0$. Using $u'(0)=u(\pi)$, one has
$$ \sqrt{\mu}A-\sqrt{\mu}B=0, Ae^{\sqrt{\mu}\pi}+Be^{-\sqrt{\mu}\pi}=0$$
From this, it is easy to see that $A=B=0$; namely, the problem does not have nonzero eigenfunction.
Case 2: $\mu<0$. Using $u'(0)=u(\pi)$, one has
$$ A\sqrt{-\mu}=0, A\sin(\sqrt{-\mu}\pi)+B\cos(\sqrt{-\mu}\pi)=0$$
From this, it is easy to see that $A=0$. In order to seek nonzero eigenfunction, set
$$ \sqrt{-\mu}=n $$
where $n=1,2,3,\cdots$. So $\mu=-n^2$ or $\lambda=-n^2-4$ and the corresponding eigenfunction is $u_n=B\cos(n x)$. It is easy to check that
$$ \int_0^\pi\cos(mx)\cos(nx)dx=0, m\neq n$$
and
$$ \int_0^\pi\cos^2(mx)dx=\frac\pi2. $$
So the eigenfunctions are orthogonal.


TITLE: Inverse of $x\sinh x$
QUESTION [3 upvotes]: I'm looking for a closed expression for the inverse of $$f(x)=x\cdot\sinh x\,.$$ It looks like there should be some combination of Lambert $W$ functions that would do it, but I can't seem to find a solution.
In the application I'm considering, $x$ is real and positive (but not very large).

REPLY [1 votes]: There is no closed solution with the known classical functions.
If one defines $\,f(x):=(x+\sqrt{1+x^2})^x\geq 1\,$ for $x\in\mathbb{R}\,$ , $\,f(-x)=f(x)\,$ ,
and $\,f^{-1}(x)\,$ is his inverse for $\,x\geq 0$, then it's possible to solve $\,y=x\sinh x\,$ : $$x_{1,2}=\pm \sinh^{-1} f^{-1}(e^y)$$

Note:
It's a bit like $\,y=g(x):=1+x^2\ge 1\,$ with $\,x_{1,2}=\pm g^{-1}(y)=\pm\sqrt{y-1}\,$ .


TITLE: Parameterization of a knotted surface?
QUESTION [6 upvotes]: I'm looking for a parameterization $(x_1(u,v),x_2(u,v),x_3(u,v),x_4(u,v))$ of a knotted sphere in $\mathbb R^4$. How might one go about finding such a parameterization?

REPLY [10 votes]: If you know how to parameterize a nontrivial knot in $R^3$ (say, the trefoil knot), you can use Artin's "spinning" construction to parameterize a nontrivial knot in $R^4$ via map $S^2\to R^4$ written in spherical coordinates on $S^2$. Take, say, the trefoil $T$ in $R^3$ parameterized by some smooth periodic function $f(\theta), 0\le \theta\le a$ where $a$ is the period. Let $L$ denote the straight line in $R^3$ through the points $f(0), f(c)$, $c=a- \epsilon$ where $\epsilon>0$ is sufficiently small (if you want to know how small is small, ask me and I can explain). I will choose the coordinates $x_1, x_2, x_3$ so that $L$ is the $x_3$-axis. Let $R_\phi$ denote the rotation  by the angle $\phi$ in $R^4$ around the plane $x_1=x_2=0$ (thus, fixing $L$). Now, consider the map
$F: [0, c]\times [0, 2\pi]\to R^4$, given by
$$F(\theta, \phi) = R_\phi\circ f(\theta)$$
Its image is a knotted 2-sphere $\Sigma$ in $R^4$. It is smooth away from the points $f(0), f(c)$. If this bothers you, it can be fixed (explicitly). Now, rescale the  interval $[0, c]$ to $[0, \pi]$ via the map $s: t\mapsto \frac{\pi}{c}t$. Then the map $$G= F\circ (s^{-1} \times Id): [0,\pi]\times [0,2\pi]\to R^4$$ parameterizes the same surface $\Sigma$ as before. Lastly, use the spherical coordinates on $S^2$ to convert the map $G$ to a homeomorphism $S^2\to \Sigma$.
This, I think, is as an explicit construction as it can be (provided you are not bothered by smallness issue for $\epsilon$).
Edit: Upon your request, smallness of $\epsilon$ is defined as follows: There exists a round ball $B$ (or a half-space) in $R^3$ with points $p=f(a-\epsilon), q=f(a)$ on its boundary such that the arc $\alpha=f([a-\epsilon, a])$ is contained in $B$ and is unknotted in $B$, i.e., is isotopic to the line segment $pq$ in $B$ via an isotopy fixing the boundary sphere of $B$. (In practical terms, you can think of the unknottedness property of $\alpha$ as assuming that $\alpha$ is a graph of a function on the segment $pq$, with values in the plane orthogonal to $pq$.)
See for instance here for details.


TITLE: Positivity of an operator
QUESTION [2 upvotes]: Consider a function $f:\mathbb{R}\to \mathbb{R}$ of class $C^1$. If $f(0)=0$ and $f'(0)>0$ it's clear that there exist some $t_0>0$ such that $f(t_0)>0$.
Now if $f:\mathbb{R}\to \mathcal{M}^{n\times n}(\mathbb{R})$ of class $C^1$, where $\mathcal{M}^{n\times n}$ are real $n\times n$ matrices, if $f(0)=0$ and if $f'(0)$ is a strictly positive defined matrix, again there will be a $t_0$ such that $f(t_0)$ is a strictly positive defined matrix.
The question is, is it true even for operators? In particular, let $f:\mathbb{R}\to \mathcal{O}$ of class $C^1$, where $\mathcal{O}$ is the set of compact self-adjoint operators on some separable Hilbert space $\mathcal{H}$. Let $f(0)=0$ and suppose that $f'(0)$ is a compact positive self-adjoint operator, is it true that there must be a $t_0$ such that $f(t_0)$ is positive?

REPLY [2 votes]: No. Counterexample: Let $H = \ell^2$ and $M : H \to H$ be given by
$$ M(x_1, x_2, \cdots, x_n , \cdots) = \left( x_1, \frac{x_2}{2}, \cdots, \frac{x_n}{n}, \cdots \right).$$
Then $M$ is compact (limits of finite rank operators), self-adjoint and positive. Next let $\varphi: \mathbb R \to \mathbb R$ be a smooth odd function so that

$\varphi(t) = t$ on $[-1,1]$,
$|\varphi (t)|\le 1.1$
$\varphi$ is decreasing on $[1.1, 2]$ and
$ \varphi(t) = 0$ on $[2, \infty)$.

For each $n$, define $\varphi_n (t) = \frac{1}{2^n }\varphi (2^n t)$. Define $ M_t:=f(t)$ by
$$ M_t (x_1,x_2, \cdots, x_n, \cdots ) = \left(\varphi _1(t) x_1, \frac{\varphi_2(t)}{2} x_2, \cdots, \frac{\varphi_n (t)}{n} x_n, \cdots\right).$$
Then $M_0 = 0$ and each $M_t$ is self-adjoint, finite rank (thus non-positive). Also, $f$ is $C^1$. Indeed one can check that
$$f'(t) (x_1,x_2, \cdots, x_n, \cdots ) = \left( \varphi_1'(t) x_1, \frac{\varphi_2'(t)}{2} x_2, \cdots, \frac{\varphi_n'(t)}{n} x_n, \cdots \right).$$
Since $\varphi_n'(0)=1$ for all $n$, we have $f'(0) = M$.


TITLE: What is the motivation for Murray-von Neumann equivalence
QUESTION [13 upvotes]: Definition: If $p,q$ are projections in a $C^*$-algebra $A$, we say that they are Murray-von Neumann equivalent, and we write $p\sim q$, if there exist $u\in A$ such that $p=u^*u$ and $q=uu^*$.

I wonder what is the motivation of this definition. It turns out that if $A$ is a matrix algebra like $M_n(\mathbb C)$, then this definition is equivalent to saying that $p$ and $q$ have the same rank. But how about the general case? Is Murray-von Neumann equivalence the most natural way to define the equivalence relation on the projections of a $C^*$-algebra in some sense?

REPLY [13 votes]: Here's one possible take on the question:
$K$-theory for $C^*$-algebras is motivated by topological $K$-theory. Topological $K_0$ for a compact Hausdorff space $X$ is the Grothendieck group of formal differences of isomorphism classes of locally trivial vector bundles over $X$, so we want the operator $K_0$-group of $C(X)$ to match this.
The Serre-Swan theorem says that every locally trivial vector bundle is complemented, so it corresponds to $P C(X, \mathbb{C}^n)$ for some $n$ and some projection in the $C^*$-algebra $C(X, M_n(\mathbb{C}))$. To think of all of these operators $P$ living in the same $C^*$-algebra, we think of them all as projections in $C(X, \mathcal{K})$, where $\mathcal{K}$ is the compact operators. An isomorphism of vector bundles $P C(X, \mathbb{C}^n), Q C(X, \mathbb{C}^n)$ amounts to a continuous choice of vector-space isomorphisms between their fibres; this is an element $V \in C(X, \mathcal{K})$ such that $V^*V = P$ and $VV^* = Q$. This indicates why Murray-von Neumann equivalence is a better choice than unitary equivalence: once you're sitting in $C(X, \mathcal{K})$, unitary equivalence happens outside your $C^*$-algebra (in its multiplier algebra).
Finally, Murray-von Neumann equivalence plays nicely with the abstract notion of rank given by a trace (when the $C^*$-algebra carries one): if $\tau$ is a trace, and $p$ and $q$ are MvN equivalent, then $\tau(p) = \tau(v^*v) = \tau(vv^*) = \tau(q)$. And the natural alternatives, namely unitary equivalence and homotopy equivalence, turn out to agree with Murray-von Neumann equivalence for projections in $\mathcal{K} \otimes A$.


TITLE: Finding order when disordering an ordered set
QUESTION [2 upvotes]: Let $S=\{a_1,a_2,\dots, a_m\}$ be some ordered set, such that $a_i<a_{i+1}$.
I find that, no matter how much I try, I can not totally disorder the set without finding some subset of the resulting disordered set where order is still preserved among its elements, which form a monotonically increasing or decreasing sequence.
After some experimentation, it seems that a set of $2^{n-1}$ elements guarantees at least some monotonically increasing or decreasing sequence of $n$ elements for any disordered set I make, with only one exception for $n=3$: $\{a_2,a_1,a_4,a_3\}$ It can be seen that no subset of $3$ elements can be chosen from this disordered set that form a monotonically increasing or decreasing sequence. However, this is the only one I have found.
I am not sure if this guess is correct, and no clue about how to prove or disprove it; any correction, counterexample, or reference about this would be really welcomed.
Thanks!

REPLY [3 votes]: By (a special case of) the Erdos-Szekeres theorem, any sequence of $(n-1)^2+1$ numbers contains an increasing or decreasing sequence of $n$ numbers.
Since $2^{n-1}\ge(n-1)^2+1$ for $n\ge6$, this proves your conjecture for these values of $n$.  It remains to check $n=4$ and $n=5$.  Counterexamples in these cases follow a simple pattern:

$6,7,8;\quad 3,4,5;\quad 1,2$;
$13,14,15,16;\quad 9,10,11,12;\quad 5,6,7,8;\quad 1,2,3,4$.

The semicolons and large spaces emphasize the structure.  In the first example, any four numbers must include two from the same group, so cannot be decreasing; and must include two from different groups, so cannot be increasing.  Same goes for five numbers in the second example.


text:
\section{QDGD Algorithm}\label{sec:algorithm}
In this section, we propose a quantized gradient based method to solve the decentralized optimization problem in \eqref{eq:main_2} and consequently the original problem in \eqref{eq:main} in a fully decentralized fashion. To do so, consider $\bx_{i,t}$ as the decision variable of node $i$ at step $t$ and  $\bz_{i,t} = Q(\bx_{i,t})$ as the quantized version of the vector $\bx_{i,t}$. In the proposed Quantized Decentralized Gradient Descent (QDGD) method, nodes update their local decision variables by combining the quantized information received from their neighbors with their local information. To formally state the update of QDGD, we first define $w_{ij}$ as the weight that node $i$ assigns to node $j$. If nodes $i$ and $j$ are not neighbors then $w_{ij}=0$, and if they are neighbors the weight $w_{ij}\geq0$ is nonnegative. At each time step $t$, each node $i$ sends its quantized $\bz_{i,t}$ variant of its local vector $\bx_{i,t} $ to its neighbors $j\in \mathcal{N}_i$ and receives their corresponding vectors $\bz_{j,t}$. Then, using the received information it updates its local decision variable according to the update

\begin{equation}\label{eq:alg_update}
    \bx_{i,t+1} =  (1 - \eps + \eps w_{ii}) \bx_{i,t} + \eps \sum_{ j \in  \mathcal{N}_i } w_{ij} \bz_{j,t} - \al \eps \gr f_i(\bx_{i,t}),
\end{equation}

where $\eps$ and $\alpha$ are positive step-sizes.

The update of QDGD in \eqref{eq:alg_update} shows that the updated iterate is a linear combination of the weighted average of node $i$'s  neighbors' decision variable, i.e.,  $\eps\sum_{ j \in  \mathcal{N}_i } w_{ij} \bz_{j,t}$, and its local variable $\bx_{i,t}$ and  gradient ${\gr} f_i(\bx_{i,t})$. The parameter $\alpha$ behaves as the stepsize of the gradient descent step with respect to local objective function and the parameter $\eps$ behaves as an averaging parameter between performing the distributed gradient update  $\eps( w_{ii}\bx_{i,t} +  \sum_{ j \in  \mathcal{N}_i } w_{ij} \bz_{j,t} - \al  {\gr} f_i(\bx_{i,t}))$ and using the previous decision variable $(1-\eps)\bx_{i,t}$. By choosing a diminishing stepsize $\alpha$ and averaging using the parameter $\eps$ we control randomness induced by exchanging quantized variables. The steps of the proposed QDGD method are summarized in Algorithm \ref{alg:QDC}.

\begin{algorithm}[t]
\caption{QDGD at node $i$}\label{alg:QDC}
\begin{algorithmic}[1]
\Require Weights $\{w_{ij}\}_{j=1}^n$, total iterations $T$
\State Set $\bx_{i,0}=0$ and compute $\bz_{i,0}=Q(\bx_{i,0})$
\For{$t=0,\cdots,T-1$}
	\State Send $\bz_{i,t}=Q(\bx_{i,t})$ to $j\in\mathcal{N}_i$ and receive $\bz_{j,t}$
        \State Compute  $\bx_{i,t+1}$ according to the update in \eqref{eq:alg_update}
\EndFor
\State \Return $\bx_{i,T}$
\end{algorithmic}
\end{algorithm}

\begin{remark}
The proposed QDGD algorithm can be interpreted as a variant of the decentralized (sub)gradient descent (DGD) method \cite{nedic2009distributed,yuan2016convergence} for quantized decentralized optimization (see Section \ref{sec:convergence}). Note that the vanilla DGD method converges to a neighborhood of the optimal solution in the presence of quantization noise where the radius of convergence depends on the variance of quantization error \cite{nedic2009distributed,yuan2016convergence,rabbat2005quantized,nedic2008distributed}. QDGD improves the inexact convergence of quantized DGD by modifying the contribution of quantized information received from neighboring noise as described in update~\eqref{eq:alg_update}. In particular, as we show in Theorem \ref{thm1}, the sequence of iterates generated by QDGD converges to the optimal solution of Problem \eqref{eq:main} in expectation.
\end{remark}

Note that the proposed QDGD algorithm does not restrict the quantizer, except for few customary conditions. However, design of efficient quantizers has been taken into consideration. Consider the following example as such quantizers.

\begin{example} \label{ex:q1}
Consider a low-precision representation specified by $\gamma \in \mathbb{R}$ and $b \in \mathbb{N}$. The range representable by scale factor $\gamma$ and $b$ bits is
$ \{ -\gamma \cdot 2^{b-1}, \cdots, -\gamma, 0, \gamma, \cdots, \gamma \cdot (2^b-1) \}$. For any $k\gamma \leq x < (k+1)\gamma$ in the representable range, the low-precision quantizer outputs

\begin{equation}
    Q_{(\gamma,b)}(x) =
    \left\{
	\begin{array}{ll}
		k\gamma  & \mbox{w.p. } 1-\frac{x-k\gamma}{\gamma}, \\
		(k+1)\gamma & \mbox{w.p. } \frac{x-k\gamma}{\gamma}.
	\end{array}
    \right.
\end{equation}

For any $x$ in the range, the quantizer is unbiased and variance bounded, i.e.  $\bE\left[Q_{(\gamma,b)}(x)\right]=x$ and $\bE \left[ \norm{Q_{(\gamma,b)}(x) - x}^2 \right]\leq\frac{\gamma^2}{4}$.
\end{example}

In Section~\ref{sec:convergence}, we formally state the required conditions for the quantization scheme used in QDGD and show that a large class of well-known quantizers satisfy the required conditions.

config: arxiv