Human-verifiable proof (no group theory needed!) that every supertwist position (all edges solved, all corners twisted in some way) must take at least 16 moves to solve:
Strategy:
For each individual edge piece, we will determine the minimum number of moves to solve it and its surrounding corner pieces (ignoring moves that are needed but that don't move the edge piece), show that this is 4 for each edge piece for a supertwist scramble, then conclude that since we need 12×4 = 48 edge piece movements in total and each move affects 3 edge pieces, every supertwist position is at least 48/3 = 16 moves away from solved.
We will label the pieces as on a 3×3×3: faces are identified by single letters, edges are identified by two faces (and hence two letters), corners are identified by three faces (and hence three letters). Where colours are mentioned, white-top green-front with the standard BOY colour scheme is assumed.
Consider an edge piece and the two corner pieces that surround its home position. We are interested only in counting the moves that affect the edge piece in consideration, so we may do moves that don't affect it "for free". For example, suppose the UF edge (white-green) is in the UF position. Then turns of any corner except UFL or UFR are free, but they also don't matter, since they affect neither the UF edge nor the UFL/UFR corners. Suppose instead the UF edge (white-green) is in the BR position (e.g. by doing UFR UBR' to a solved cube). Then UBL, DBL, DFL, DFR are free (but useless); UFL and UFR can affect the orientation of the neighbouring corners for free; UBR and DBR move the edge piece under consideration (and are not free).
---
Claim: If the edge piece is solved and exactly one of its neighbouring corners is twisted, then the edge piece needs to be moved at least 2 times.
Proof: Any move of a non-neighbouring corner cannot fix the twist, while turning a neighbouring corner once moves the edge piece away from solved. Hence at least 2 moves are needed.
(In fact the only way to solve it in 2 moves is to turn the solved corner (1 move), fix the corner twist (free because it's no longer touching the edge), then turn the originally-solved corner back (1 move). We don't actually need this to prove the next thing; it's just to give a flavour of how the proof works.)
---
Claim: If the edge piece is solved and both of its neighbouring corners are twisted, then the edge piece needs to be moved at least 4 times.
Proof: Without loss of generality, suppose the edge piece in question is the UF (white-green) piece, so the two neighbouring corners are UFL and UFR. The UFL corner cannot be twisted while attached to the UF edge, so at least 1 move is needed to separate the edge from UFL and 1 more move is needed to reattach it. Likewise for the UFR corner. It remains to show that these four moves must be distinct moves (i.e. you cannot use the same move for two different purposes).
Obviously the move that attaches to UFL cannot coincide with the move that separates from UFL (resp. for UFR). The move that attaches to / separates from UFL must be of one of the corners adjacent to UFL, i.e. UFR, DFL, or UBL; likewise, the move that attaches to / separates from UFR must be of UFL, DFR, or UBR. These are disjoint categories, so the UFL-affecting moves cannot coincide with the UFR-affecting moves. Therefore at least four distinct moves that affect the key edge piece must be used.
---
On a supertwist position, every edge piece needs to be moved at least 4 times. Since there are 12 edge pieces, the total number of edge piece movements must be at least 12×4 = 48. Since each move moves only 3 pieces, the minimal number of moves to effect 48 piece movements must be at least 48/3 = 16. This concludes the proof.
---
We can also apply this logic to other pure twist scrambles, leading us to a lower bound of 2n moves for a scramble with all solved edges and exactly n twisted corners. This is a fairly loose lower bound for small n; if I'm not mistaken, 1-twist needs 8 moves and the 2-twist positions need at least 10 moves.
This can also be used to provide a lower bound for arbitrary scrambles in a human-calculable way, although the lower bound is in general not very strong. For example, consider the checkerboard pattern, which is known to be 16 moves optimal. With this strategy, each piece takes 3 movements (even without caring about solving the corners), so we get a lower bound of 12 moves.
Strategy:
For each individual edge piece, we will determine the minimum number of moves to solve it and its surrounding corner pieces (ignoring moves that are needed but that don't move the edge piece), show that this is 4 for each edge piece for a supertwist scramble, then conclude that since we need 12×4 = 48 edge piece movements in total and each move affects 3 edge pieces, every supertwist position is at least 48/3 = 16 moves away from solved.
We will label the pieces as on a 3×3×3: faces are identified by single letters, edges are identified by two faces (and hence two letters), corners are identified by three faces (and hence three letters). Where colours are mentioned, white-top green-front with the standard BOY colour scheme is assumed.
Consider an edge piece and the two corner pieces that surround its home position. We are interested only in counting the moves that affect the edge piece in consideration, so we may do moves that don't affect it "for free". For example, suppose the UF edge (white-green) is in the UF position. Then turns of any corner except UFL or UFR are free, but they also don't matter, since they affect neither the UF edge nor the UFL/UFR corners. Suppose instead the UF edge (white-green) is in the BR position (e.g. by doing UFR UBR' to a solved cube). Then UBL, DBL, DFL, DFR are free (but useless); UFL and UFR can affect the orientation of the neighbouring corners for free; UBR and DBR move the edge piece under consideration (and are not free).
---
Claim: If the edge piece is solved and exactly one of its neighbouring corners is twisted, then the edge piece needs to be moved at least 2 times.
Proof: Any move of a non-neighbouring corner cannot fix the twist, while turning a neighbouring corner once moves the edge piece away from solved. Hence at least 2 moves are needed.
(In fact the only way to solve it in 2 moves is to turn the solved corner (1 move), fix the corner twist (free because it's no longer touching the edge), then turn the originally-solved corner back (1 move). We don't actually need this to prove the next thing; it's just to give a flavour of how the proof works.)
---
Claim: If the edge piece is solved and both of its neighbouring corners are twisted, then the edge piece needs to be moved at least 4 times.
Proof: Without loss of generality, suppose the edge piece in question is the UF (white-green) piece, so the two neighbouring corners are UFL and UFR. The UFL corner cannot be twisted while attached to the UF edge, so at least 1 move is needed to separate the edge from UFL and 1 more move is needed to reattach it. Likewise for the UFR corner. It remains to show that these four moves must be distinct moves (i.e. you cannot use the same move for two different purposes).
Obviously the move that attaches to UFL cannot coincide with the move that separates from UFL (resp. for UFR). The move that attaches to / separates from UFL must be of one of the corners adjacent to UFL, i.e. UFR, DFL, or UBL; likewise, the move that attaches to / separates from UFR must be of UFL, DFR, or UBR. These are disjoint categories, so the UFL-affecting moves cannot coincide with the UFR-affecting moves. Therefore at least four distinct moves that affect the key edge piece must be used.
---
On a supertwist position, every edge piece needs to be moved at least 4 times. Since there are 12 edge pieces, the total number of edge piece movements must be at least 12×4 = 48. Since each move moves only 3 pieces, the minimal number of moves to effect 48 piece movements must be at least 48/3 = 16. This concludes the proof.
---
We can also apply this logic to other pure twist scrambles, leading us to a lower bound of 2n moves for a scramble with all solved edges and exactly n twisted corners. This is a fairly loose lower bound for small n; if I'm not mistaken, 1-twist needs 8 moves and the 2-twist positions need at least 10 moves.
This can also be used to provide a lower bound for arbitrary scrambles in a human-calculable way, although the lower bound is in general not very strong. For example, consider the checkerboard pattern, which is known to be 16 moves optimal. With this strategy, each piece takes 3 movements (even without caring about solving the corners), so we get a lower bound of 12 moves.
