TITLE: What is the exact relationship between scale invariance and renormalizability of a theory?
QUESTION [6 upvotes]: I have often read that renormalizability and scale invariance are somehow related. For example in this tutorial on page 12 in the first sentence of point (7), self similarity (= scale invariance ?) is referred to as the non-perturbative equivalent of renormalizability.
I don't understand what this exactly means. Can one say that all renormalizable theories are scale invariant but the converse, that every scale invariant theory is renormalizable too, is not true? I'm quite confused and I'd be happy if somebody could (in some detail) explain to me what the exact relationship between scale invariance and renormalizability is.

REPLY [3 votes]: There is a relation between scaling and renormalization, but not between scaling invariance and renormalization.
Scaling is possible for every polynomial Lagrangian density. In scaling, one transforms space-time, fields and coupling constants by suitable powers of a dilation factor in a way that preserves the action. Scaling is the reason for the existence of the renormalization (semi)group. It implies that the parameter defining the mass scale in a renormalization prescription is redundant.
On the other hand, scaling invariance means that the coupling constants are independent of the dilation factor, which is a rare situation. For example, QED is renormalizable and has a scaling operation affecting the electron mass, hence is not scale invariant.
Self-similarity is a property of fixed points (critical points) of a renormalization group mapping. However, in QFT this self-similarity is not a property of a physical theory but of the regularizations at different energy scales. (This energy has nothing to do with the mass scale in the renormalization prescription, though some formulas at 1 loop look very similar.)


TITLE: Why the kernel is a normal subgroup?
QUESTION [0 upvotes]: Let $G$ be a group acting on a nonempty set $A$. Why the kernel of the action is a normal subgroup of $G$?

REPLY [3 votes]: Let $\;\phi:G\to H\;$ be a group homomorphism, and let $\;x\in\ker\phi\;,\;\;g\in G\;$ , then
$$\phi(g^{-1}xg)=\phi(g^{-1})\phi(x)\phi(g)=\phi(g)^{-1}\cdot1\cdot\phi(g)=\phi(g)^{-1}\phi(g)=1\implies$$
$g^{-1}xg\in \ker\phi\;$ whenever $\;x\in\ker\phi\;,\;\;g\in G\;\iff\;\ker\phi\lhd G$


TITLE: What is the most efficient algorithm for deciding if an element is the least in its orbit?
QUESTION [8 upvotes]: Given a group $G$ acting on a set $X$ with a total order $\leq$ and an $x\in X$, what is the most efficient algorithm for deciding whether or not x is the least element in its orbit, in other words, deciding if $ min(Gx) = x$?
My motivation comes from SMT solving where there has been some interest in automatically breaking symmetries. Adding symmetry breaking predicates often result in a large clause set therefore I am interested in the possibility of handling this as a lazy theory propagation.
The above description is perhaps too general, and as noted by sid, NP-hard. A possible simpler task is, given a group of permutations of strings of length $n$ encoded as a set of generators and a string $x$ of length $n$. What is the most efficient algorithm for deciding if that string is the lexicographically smallest in its orbit?

REPLY [9 votes]: For general equivalence relations, not those arising from permutation group actions, even finding lexicographically least is still "too" general. Finding the lexicographically smallest element in an equivalence class can be $NP$-hard (in fact, $P^{NP}$-hard) - even if the relationship has a polynomial-time canonical form [1].
However, for permutation group orbit problems as you describe, deciding whether two points lie in the same orbit is not likely to be $NP$-hard: it is in $NP \cap coAM$, and hence not $NP$-hard unless the polynomial hierarchy collapses to the second level.
A canonical form for graph isomorphism is also a special case of the second problem you state. The best known canonical form for graph isomorphism runs in time $2^{\tilde{O}(\sqrt{n})}$ [2].
Since you said in the comments that any canonical form will do, you might also be interested in my paper with Lance Fortnow [3]: in its currently generality, I think your question is related to our results. We show that if every equivalence relation decidable in $P$ has a canonical form in $P$, then "bad" consequences result, such as $NP = UP = RP$, which in particular implies that the polynomial hierarchy collapses down to $BPP$. On the other hand, the equivalence relations you're interested in may not be in $P$, but this result suggests that even if it lies in a higher complexity class other hard problems may still stand in your way.
So I think if you want some better upper bounds you really need the problem to be more specific.
[1] Andreas Blass and Yuri Gurevich. Equivalence relations, invariants, and normal forms. SIAM J. Comput. 13:4 (1984), 24-42.
[2] László Babai and Eugene M. Luks. Canonical labelings of graphs. STOC 1983, 171-183.
[3] Lance Fortnow and Joshua A. Grochow. Complexity classes of equivalence problems revisited. Inform. and Comput. 209:4 (2011), 748-763. Also available as arXiv:0907.4775v2.


text:
\section{Conclusions and future work}
\label{sec:conclusions}

In this paper, we have presented a technique for solving two-player,
zero-sum finite state stochastic games with infinite strategies and
polynomial payoffs. We established the existence of equilibria for
such games. As a by-product we got an algorithm that converged to
unique value vector of the game (however this algorithm does not seem
to have very attractive convergence rates). We focused mainly on the
case where the single-controller assumption holds. We showed that the
problem can be reduced to solving a system of univariate polynomial
inequalities and moment constraints. We used techniques from the
classical theory of moments and sum-of-squares to reduce the problem
to a semidefinite programming problem. By solving a primal-dual pair
of semidefinite programs, we obtained minimax equilibria and optimal
strategies for the players.

It is known that finite-state, finite action, two-player zero-sum
games which satisfy the \emph{orderfield} property \cite{Raghavan},
\cite{Partha} may be solved via linear programming.  The
single-controller case, games with perfect information, switching
controller stochastic games, separable reward-state independent
transition (SER-SIT) games and additive games all satisfy this
property. We intend to extend these cases to the infinite strategy
case with polynomial payoffs. General finite action stochastic games
which do not satisfy the orderfield property still have an interesting
mathematical structure, but efficient computational procedures are not
available. Developing such procedures present an interesting direction
of future research.

config: arxiv


TITLE: Metrizability of a compact Hausdorff space whose diagonal is a zero set
QUESTION [7 upvotes]: Let $X$ be a compact Hausdorff space and suppose the diagonal in $X\times X$ is the zero set of a nonnegative continuous real-valued function.  Why does this imply $X$ is metrizable?

REPLY [8 votes]: $\newcommand{\cl}{\operatorname{cl}}$Suppose that the diagonal $\Delta$ in $X\times X$ is the zero set of a continuous non-negative function $f:X\times X\to\Bbb R$. (Continuity is essential.) For $n\in\Bbb N$ let $U_n=\{\langle x,y\rangle\in X\times X:f(\langle x,y\rangle)<2^{-n}\}$; clearly $U_n$ is open in $X\times X$. For each $x\in X$ and $n\in\Bbb N$ there is an open $B(x,n)\subseteq X$ such that
$$\langle x,x\rangle\in B(x,n)\times B(x,n)\subseteq U_n\;.$$
For each $n\in\Bbb N$ let $\mathscr{U}_n=\{B(x,n):x\in X\}$; $\mathscr{B}_n$ is an open cover of $X$, so there is a finite $F_n\subseteq X$ such that $\mathscr{B}_n=\{B(x,n):x\in F_n\}$ covers $X$. Let $\mathscr{B}=\bigcup_{n\in\Bbb N}\mathscr{B}_n$; then $\mathscr{B}$ is a countable family of open sets in $X$. I claim that $\mathscr{B}$ is a base for the topology of $X$; if so, then $X$ is a second countable compact Hausdorff space and is therefore metrizable by the Uryson metrization theorem.
Suppose that $V$ is a non-empty open set in $X$, and let $x\in V$. Define $f_x:X\to\Bbb R:y\mapsto f(x,y)$, and for $n\in\Bbb N$ let $G(n,x)=\{y\in X:f_x(y)<2^{-n}\}$. Suppose that for each $n\in\Bbb N$ there is an $x_n\in G(x,n)\setminus V$, and let $\sigma=\langle x_n:n\in\Bbb N\rangle$; then $\langle f_x(x_n):n\in\Bbb N\rangle\to 0$. $X$ is compact, so $\sigma$ has a cluster point $y$. Since $f_x$ is continuous, it’s easily checked that $f_x(y)=0$ and hence that $y=x$. But this is impossible: $V$ is an open nbhd of $x$ that contains no term of $\sigma$. This contradiction shows that there must be some $n\in\Bbb N$ such that $G(x,n)\subseteq V$. It follows that $\{G(x,n):n\in\Bbb N\}$ is a local base at $x$.
Now fix $x\in X$, and let $V$ be any open nbhd of $x$. There is an $n\in\Bbb N$ such that $G(x,n)\subseteq V$, and there is a $y\in F_n$ such that $x\in B(y,n)$. Suppose that $z\in B(y,n)$; then $$\langle x,z\rangle\in B(y,n)\times B(y,n)\subseteq U_n\;,$$ so $f_x(z)=f(\langle x,z\rangle)<2^{-n}$, and $z\in G(x,n)\subseteq V$. Thus, $x\in B(y,n)\subseteq V$, where $B(y,n)\in\mathscr{B}$, so $\mathscr{B}$ is indeed a countable base for $X$, and $X$ is therefore metrizable.


TITLE: What is the cause of gravitional force of attraction?
QUESTION [1 upvotes]: Ok,this is a silly question. But for quite long I have been thinking about this. What is gravitation all about?? My book directly writes since force of gravitation is directly proportional to the masses and inversly proportional to the square of the distance ie. $$F = G\frac{M_1 . M_2}{r^2}$$ . So is this gravitation all about? What is the cause of it? The book then says

We are not in the scope in classical approach so as to discuss the cause of this. However,as a matter of fact that if there are more than one mass,then there is gravitation as it is their fundamental property.( Cause of gravitation can be attributed to exchange of non-classical particles between the masses) .

Then it ended the talkings. What are those non-classical particles? Why and how are they exchanged? So far I have studied physics , I never found such weird phenomenon like this. I want to know what is the cause of gravitation and what is the cause of exchange of those so-called non-classical particles? And how do they do it?

REPLY [7 votes]: Ultimately, the only thing that can explain a physical theory is a better theory. Newton's force law used to be the entire theory of gravitation up until the early 1900's. Newton himself had no explanation for what "caused" the force.
Einstein gave us General Relativity, which describes how gravity is the geometry of space and time. In GR, energy and momentum curve spacetime, and objects simply follow the straightest possible path through the curved spacetime! So Newton's law is "explained" by GR.
With the success of Quantum Field Theory at describing the other three fundamental forces (electromagnetism, weak nuclear, and strong nuclear), physicists have been trying very hard to create a quantum description of gravity, though none have been completely successful so far. In QFT each force is described by a field. For example, the electromagnetic field. When the field is "excited," or in other words when the field goes to a higher energy state, the excitations of this field are called photons. When you run through the math of QFT, you find that two like charges placed in the photon field will repel each other with a force that varies as $1/r^2$! This is because the two charges raise the energy state of the field. Similarly, what we do know is that if you put two objects in a simplified massless spin-2 field, you get an attractive force between the objects that varies as $1/r^2$! The force comes from each object coupling to the field and lowering its energy. Excitations of this field are called "gravitons." There is as of yet no direct evidence that gravitons exist, and it's highly unlikely that there will be any any time soon given how weakly they are predicted to interact.


TITLE: Finding inverse with parameter
QUESTION [0 upvotes]: How can I find $f^{-1}(-1)$ of $f(x)=x^3+2x^2+4ax+4$? To be honest I don't know where to start from.

REPLY [1 votes]: $f^{-1}(-1) = b \implies f(b) = -1 \implies b^3+2b^2+4ab + 4 = -1 \implies b^3+2b^2+4ab+5 = 0$. Thus $b$ is the solution of this cubic equation in $a$. The solutions are well known and is known as Viete's theorem that can be looked up in wikipedia or any book on polynomial equations in the press or online nowadays.