Disclaimer: This is an old incomplete answer, now aged multiple years. I started this before I had any formal math education and I never came back to finish this.
To make our lives easier, we can separate the pieces by 3 types:
Edges (3 stickers)
Sides (2 stickers)
Centers (1 sticker)
Also note that im observing a cube with Yellow and Black( I call it White later on) colors for the top and bottom sides as my default color scheme.
(Other pieces follow Red, Blue, Orange, Green)
For the $3\times3\times3$ Rubik's cube, first we can solve for the middle parts.
We can conclude that if the color scheme is known, that all obscured centers can be determined if we have at least 2 neighbour ones.
This means we can peel off 4 centers if we keep 2 neighbour ones. This can be checked by playing with its own cube or simply by following the laws of legal positions and using something like a solver help you out. (This is because centers can't be really switched, but the pieces around them can so that it looks that way)
Then lets see how many stickers from the edge pieces can be obscured or peeled off, since any configuration of $n\times n\times n$ always has exactly 8 edges.
We can list them by the colors they contain:
(Red, Blue, Green, Orange, Yellow, White)
$$ R,G,Y $$
$$ R,G,W $$
$$ R,B,Y $$
$$ R,B,W $$
$$ O,G,Y $$
$$ O,G,W $$
$$ O,B,Y $$
$$ O,B,W $$
If you want to know how many stickers can be peeled off and still be able to identify each corner, you can ask yourself; How many stickers you can take so that when putting them back, you have only one possible way to do so?
I have found out the maximum number of 12 out of 24 stickers; by taking all R or O, then all B or G and finally all Y or W.
Here is an example:
$$ -,-,- $$
$$ -,-,W $$
$$ -,B,- $$
$$ -,B,W $$
$$ O,-,- $$
$$ O,-,W $$
$$ O,B,- $$
$$ O,B,W $$
Now by shuflling the order and rotation of all 8 edges in every way possible, there will be only one way to stick the removed stickers, thus you still can identify the pieces.
Now the Side pieces, which might be a bit tricky.
On the $3\times3\times3$ Rubik's cube, there are 12 Edge pieces:
$$ G,R $$
$$ R,B $$
$$ B,O $$
$$ O,G $$
$$ Y,G $$
$$ G,W $$
$$ W,B $$
$$ B,Y $$
$$ R,W $$
$$ W,O $$
$$ O,Y $$
$$ Y,R $$
Now you can try to do the same thing.
Firstly I tried to remove all White stickers, then it allows me to take one color from $Y,?$ pieces other than yellow, and after that nothing more can be taken without providing multiple solutions for the edges; so that was 5 stickers.
Then after other failed attempts, I found you can remove 6 stickers; one of each color so that there aren't multiple stickers of the same color standing without their second color, and I'm kinda sure it can't be done with more than 6 here.
If someone can do better here, please let me know.
So if I haven't made a mistake, for the $3\times3\times3$ Rubik's cube you can remove total of $12+6+4 = 22$ out of 54 stickers top (following the things I pointed out) without losing any information about the cube's states.
The $2\times2\times2$ Rubik's cube is made of only 8 edge pieces, so 12 out of 24 stickers can be removed here.
We can now try to generalize this to other $n\times n\times n$ cubes.
We now know that we can for;
$n=2$ take 12 out of 24
$n=3$ take 22 out of 54
For any $n\times n\times n$ cube, we always have 8 edges, so thats $+12$ obscured stickers.
For the side pieces, we have $n$ of each piece (sorted set of pieces):
$$ W,R $$
$$ W,B $$
$$ W,G $$
$$ W,O $$
$$ Y,R $$
$$ Y,B $$
$$ Y,G $$
$$ Y,O $$
$$ R,B $$
$$ R,G $$
$$ O,B $$
$$ O,G $$
There is nothing more to do here than apply the same thing I did in $3\times 3\times 3$ cube;
Remove 6 stickers, one of each color so that there aren't multiple stickers of the same color standing without their second color and do that for each new set of the side pieces.
This provides us with $6\times(n-2)$ pieces more to obscure.
Again, if you can do better with the sorted set I provided, please let me know.
So far then, the number of stickers we can obscure is: $$12+6\times(n-2)+C$$
Where $C$ is the number of "mobile" and "immobile" centers we can obscure, that appear after $n>3$ and have yet to be figured out.
(when $n=3$ then $c=4$ )
So now, the center pieces at $4\times 4\times 4$ cube and every other with $2k$ sides ($k>1$) are different than every $2k+1$ sided cubes;
The $2k+1$ like our standart $3\times3\times3$ cube have 6 "real centers" which are immobile and $4$ out of $6$ can be obscured, the rest one-sticker centers here are "mobile" and behave differently when being rotated.
Same goes for all of centers which are all "mobile" in $2k$ cubes.
How many of these mobile centers can be obscured? I would say for a starting bound, all of one color which is then:
$C = (n-2)^2$ for $n>3$
And gives us finally:
$$12+6\times(n-2)+(n-2)^2$$
Pieces we can surely obscure.
I haven't yet started checked if more can be obscured on these centers, but thats because its now end of the day and I don't have any more time, and now decided to post my progress so far.
I think you could take it from here to finish up the generalization and try to see if it is possible to obscure more than $(n-2)^2$ stickers using the color scheme and legal permutations, so maybe separate formulas for $2k$ and $2k+1$ can be found.
Update
Actually I don't think the mobile centers should provide us with any additional problems, thus we can take for $C$ that it is: $ = (n-2)^2 \times 4$ Since we need only 2 full center colors that will tell us the rest, most easily after solving the cube to its solved state.
Then we have: $$12+6\times(n-2)+4\times(n-2)^2$$
I have classes to be on early tomorrow morning now, so good night.
Edit: This should be computed and checked to make sure I haven't made
a mistake somewhere.
It is possible to flip a single card in one direction without affecting any other cards, like this:
A B C B C a D C a C a d B a d a d b C d b D B C a B C
D E F D E F G E F G E F C E F C E F G E F G E F D E F
G H I G H I b H I b H I G H I G H I A H I A H I G H I
L U L D L U RR D
Here only moves of the top row and left column are used to flip the card in the top left corner horizontally.
By applying the same moves to different rows/columns you can flip any card, and by applying the moves 90 degrees rotated you can flip any card along the other axis.
This means that for any permutation of the cards, all $4^9$ orientations of those cards is possible.
However, not all $9!$ permutations are possible. Every move is a 3-cycle, which is a permutation with even parity. Combining even permutations only results in even permutations, so no odd permutations can be achieved. It is fairly easy to show that any even permutation is solvable using the 3-cycles you have available (for example by using the well-known theorem that the 3-cycles of the form $(1,2,k)$ generate all even permutations).
The total number of achievable states is therefore $4^9\cdot\frac{9!}2 = 47,563,407,360$, and a randomly chosen shuffled deck of cards has a $50\%$ probability of being solvable.
You can fix this problem by making two cards identical, for example by making cards 8 and 9 blank apart from their colours. By doing that, every shuffled deck becomes solvable because it becomes possible to swap any two numbers. This is because a swap of two numbered cards can be combined with a swap of the two identical blank cards, and such a double-swap is an even permutation and therefore achievable using the moves of the game. Note that the number of permutations is still $9!/2$, so having two unnumbered cards does not reduce the number of solvable positions of the game.
Edit:
For even grid sizes you should still use two blank cards, but it is for a slightly more complicated reason.
If you only look at the permutations of the numbers when both dimensions of the grid are even, then then every permutation can be reached/solved. So you'd think that no blank cards are needed in that case. However, something interesting happens with the orientations when the dimensions are even. Every move changes the parity of the permutation, but also does exactly one card flip. So the total number of card flips will be even or odd, and that must match the parity of the permutation. Both parities are affected by every move, they are equal (both even) in the solved state, so they will remain equal to each other throughout the game and must be equal for the position to be solvable.
Having two cards without numbers will still ensure that every shuffled deck will lead to a solvable position, without reducing the number of positions that can be played.
Something similar happens if only one of the dimensions is odd, but then it is not the total number of flips but the number of flips in the even direction that has to match parity with the permutation. Flips along the odd direction can be done in essentially the same way as in the 3x3 without changing the permutation. So again, using two unnumbered cards will allow the use of a shuffled deck.
In this last case with an even by odd sized grid, then there is a different way to fix the shuffled deck problem. Instead of two unnumbered cards, you could instead have one anomalous card which does not change when flipped over in the even direction. Normally it would be impossible to flip just a single card in the even direction without affecting the numbers (it would have to be an odd permutation of the numbers to match the odd card flip, so some numbers would have to be moved). It is possible however to combine the flip of that single card with a flip of the anomalous card. Flipping both cards can be done without affecting the number permutation, and since the flip of the anomalous card is not visible it is just as if a single card was flipped. Therefore the presence of this anomalous card makes every shuffled state solvable.
Best Answer
book http://www.amazon.com/Irrational-Numbers-Carus-Mathematical-Monographs/dp/0883850389
page 37, Theorem 3.9, due to Lehmer: given integers $n > 2$ and $k,$ then $$ 2 \cos \left( \frac{2k \pi}{n} \right) $$ is an algebraic integer of degree $\phi(n)/2.$
Twice your cosine is $$ t = \sqrt 2 - \frac{1}{2}. $$ This satisfies $$ 4 t^2 + 4 t - 7 = 0 $$ and is an algebraic number but not an algebraic integer. See https://en.wikipedia.org/wiki/Algebraic_integer#Non-example