Why are symmetries in phase space generated by functions that leave the Hamiltonian invariant?

I recently spent a lot of time thinking about this stuff and wrote a little document which I put on my website here (under the title "Visualizing the Inverse Noether Theorem and Symplectic Geometry"). So I will begin by first addressing your specific question of how the symmetries of the Hamiltonian and Lagrangian are connected. However, I also want to address the deeper sub-question: what is a "symmetry" exactly, and how should we think about them? This part of my answer will be a little bit like a manifesto.

Main Question: Invariance of Lagrangian

Any transformation that changes the Lagrangian by a total derivative is called a "symmetry" (sometimes a "quasi symmetry"). Noether's theorem can be used extract a conserved quantity using this symmetry. In the Hamiltonian framework, you then find that this conserved quantity "generates" the original symmetry.

It is easier to see why this works out in the "Hamiltonian Lagrangian" formalism, where the Lagrangian $L_H$ is a function of momentum and position.

$$ L_H(p_i, q_i, \dot q_i) = p_i \dot q_i - H(q_i, p_i) $$ (Here, $i = 1\ldots n$ and summation is implied when indices are repeated.)

Now consider we have some conserved quantity $Q$; $$ \{ Q, H \} = 0. $$ This "generates" the infinitesimal transformation $$ \delta q_i = \varepsilon \frac{\partial Q}{\partial p_i} \hspace{1 cm} \delta p_i = -\varepsilon \frac{\partial Q}{\partial q_i} $$ Now, if we imagine that $\varepsilon$ is some tiny time dependent function, i.e. $\varepsilon = \varepsilon(t)$, we can use it to vary the action of a path. Assuming the boundary conditions $\varepsilon(t_1) = \varepsilon(t_2) = 0$, on solutions to the equations of motion we have

\begin{align*} 0 &= \delta S \\ &= \int_{t_1}^{t_2} \delta L_H dt \\ &= \int_{t_1}^{t_2} \Big( -\varepsilon \frac{\partial Q}{\partial q_i} \dot q_i + p_i \frac{d}{dt} \big( \varepsilon \frac{\partial Q}{\partial p_i} \big) - \varepsilon\{H, Q\} \Big) dt \\ &= \int_{t_1}^{t_2} \Big( -\varepsilon \frac{\partial Q}{\partial q_i} \dot q_i - \dot p_i \varepsilon \frac{\partial Q}{\partial p_i} \Big) dt \\ &= -\int_{t_1}^{t_2} \varepsilon \dot Q dt \end{align*} We can therefore see that on solutions to the equations of motion, $\dot Q = 0$. This is just Noether's theorem.

We may now wonder how this symmetry transformation affects $L_H$ when $\varepsilon$ is a constant. We see that it changes it exactly by a total derivative, as expected:

\begin{align*} \delta L_H &= - \frac{\partial Q}{\partial q_i} \dot q_i - p_i \frac{d}{dt} \Big( \frac{\partial Q}{\partial p_i} \Big) + \{ H, Q\} \\ &= - \frac{\partial Q}{\partial p_i} \dot q_i - \dot p_i \frac{\partial Q}{\partial p_i} + \frac{d}{dt} \Big( p_i \frac{\partial Q}{\partial p_i} \Big) \\ &= \frac{d}{dt} \Big( p_i \frac{\partial Q}{\partial p_i} - Q\Big) \end{align*}

So we can see that $L_H$ necessarily changes by a total derivative. Let me now point out an interesting aside. When the quantity $p_i \frac{\partial Q}{\partial p_i} - Q = 0$, the total derivative is $0$. This happens when the conserved quantity is of the form $$ Q = p_i f_i(q). $$ Note that in the above case, $$ \delta q_i = f_i(q) $$ That is, symmetry transformations which do not "mix up" the $p$'s with the $q$'s have no total derivative term in $\delta L$.

Manifesto: What really is a "symmetry"?

You said something very interesting in your question statement which I have heard many physicists say.

Therefore we can reverse the role of the two functions in the Poisson bracket above $\{F,H\}=0↔\{H,F\}=0.$ In words, this second equation tells us that for any conserved quantity F, its action on the Hamiltonian H is zero. In other words, F generates as symmetry. This is exactly Noether's theorem.

Now, the word "symmetry" is pretty slippery. Earlier in this answer I said that a symmetry is something that changes the Lagrangian by a total derivative. However, that is a pretty obtuse definition for symmetry. In your question, you refer to a symmetry as a transformation which keeps $H$ constant. That definition is also a bit obtuse.

In my opinion, a "symmetry" in classical mechanics is an operation that commutes with time evolution. So, for example, if your system has a "rotational symmetry," then rotating your system, then time evolving it, will result in the same final state as time evolving it, then rotating it.

Note that not every "symmetry" in modern parlance fits this description. For instance, think about the scaling symmetry of a free particle. A free particle will travel along a straight line at a constant velocity: $\vec x = \vec v t + \vec a$. If we multiply the particle's coordinate by some constant $b$, then $\vec x = b (\vec v t + \vec a).$ This is another valid path the particle may take, so scaling is a symmetry of the equations of motion. While that is true, scaling is NOT a "symmetry" given my preferred definition. However, this naive scaling symmetry does not change the Lagrangian by a total derivative, so it has no associated conserved quantity. (I am trying to convince you that my preferred definition is the more useful one.)

What about Lorentz boosts? Those also fit my definition, but there is a tiny complication. When you perform a Lorentz boost, you must change your definition of time. So if you boost and then time evolve, you should end up with the same final state as if you time evolved and then boosted, as long as you correctly account for the fact that the definition of "time" changes after a boost. So the case of special relativity is a little subtle.

I do not think that

$$ \{ Q, H \} = 0 = \{H, Q\} $$ is the correct way to understand Noether's theorem in Hamiltonian mechanics. In my opinion, the avatar is the "inverse Noether theorem" $$ X_H(Q) = 0 \implies [X_H, X_Q] = 0. $$ In the above expression, $X_H$ is the Hamiltonian vector field "generated by $H$" and $[\cdot, \cdot]$ is the vector field "Lie Bracket" defined by $$ [X_H, X_Q] = X_H X_Q - X_Q X_H. $$ Note that I am also using the notation where vector fields act on functions as a differential operator, so for example $$ X_H (Q) = \{Q, H\}. $$

$X_H(Q)$ should be thought of as the change in $Q$ that comes from "flowing along" $X_H$, i.e. $$ \dot Q = X_H(Q). $$ The "proof" of Noether's theorem in Hamiltonian mechanics is just the Jacobi identity. $$ \{ \{g, h\}, f\} + \{ \{h, f\}, g\} + \{ \{f, g\}, h\} = 0 $$ Rearranging a bit, also using the anti symmetry of the Poisson bracket $$ \{f, \{h, g\}\} = \{ g, \{h, f\}\} - \{ h, \{g, f\}\} $$ we can use definition of our Hamiltonian vector fields acting on a test function $f$ to write $$ X_{\{h, g\}} (f) = [X_g, X_h](f) $$ and finally $$ X_{\{h, g\}} = [X_g, X_h]. $$ This demonstrates that if $Q$ is conserved, i.e. $\dot Q = X_H(Q) = \{Q, H\} = 0$, then we have a symmetry $[X_H, X_Q] = X_{\{Q, H \}} = X_0 = 0$.

Note that the Lie bracket can be shown to give the "failure" of flows to commute infinitesimally.

Perhaps I have been introducing notation too quickly, so I should mention I discuss this at a more reasonable pace in my notes linked above.

Anyway, once you start thinking in terms of commuting flows, you realize that "symmetries" in classical mechanics are directly analogous to "symmetries" in quantum mechanics.

In quantum mechanics, we capture the above statement mathematically (suppressing $\hbar$) as $$ [e^{-i t \hat H}, e^{- i \theta \hat J}] = 0. $$ The above equation can actually be understood as four closely related equations.

1. $[e^{-i t \hat H}, e^{- i \theta \hat J}] = 0$: Rotating and then time evolving a state is the same as time evolving and then rotating. (We have a symmetry.)

2. $[e^{-i t \hat H},\hat J] = 0$: The angular momentum of a state does not change after time evolution. (Angular momentum is conserved.)

3. $[\hat H, e^{- i \theta \hat J}] = 0$: The energy of a state does not change if the state is rotated.

4. $[\hat H, \hat J] = 0$: If you measure the angular momentum of a state, the probability that the state will have any particular energy afterwards will not change. The reverse is also true. ($\hat H$ and $\hat J$ can be simultaneously diagonalized.)

We can see that symmetries and conservation laws are interrelated in many ways far beyond the simple statement "symmetries give conservation laws."

Rather amazingly, three of these four statements about quantum mechanics also have direct analogs in classical mechanics!

1. $[X_H, X_J] = 0$: Rotating and then time evolving a state is the same as time evolving and then rotating. (We have a symmetry.)

2. $X_H(J) = 0$: The angular momentum of a state does not change after time evolution. (Angular momentum is conserved.)

3. $X_J(H) = 0$: The energy of a state does not change if the state is rotated.

4. $\{H, J\} = 0$: No classical meaning I can think of. (Can you think of one?)

In my opinion, once you think about "symmetries" of mechanics in terms of commutativity, many disparate facts start to fit together in a more pleasing and unified way. However, in other areas of physics, "symmetry" means something totally different (like gauge symmetry). I think you always need to be very careful with this important yet slippery word...