Hi BigBadWool, are you talking about making contact with the public school or the gifted private school? I imagine that a different approach would be needed for each school, but I don't have any experience of US schools (based in the UK). I think that looking big for his age will also be a bonus for early K entrance, but I think that you will need to ensure that they can accommodate his needs or (in my opinion) it could adversely affect the way your DS feels about school if it is just too easy and he is bored. I think that it also depends on his personality, I know that my DS7 has very low thresholds for boredom and actually becomes very miserable, whereas my younger one enjoys the social aspect of school more than the work and doesn't seem to mind going over things that he can already easily do.
It might be good to have a chat to your DS to see what he wants to get out of school (is it tricky work, being around friends etc?) and then manage his expectations accordingly if you decided to go along the school route.
I know that a lot of people here have had lots of success with home schooling and it would be interesting to get their opinions, I am not sure how easy it will be to go back into a school environment at a later stage if your DS is so far ahead. People with US experience will be able to help.
I do remember reading somewhere that 4 is still a bit young to get tested, but I think that it depends on the test. My DS did the Stanford-Binet LM when he turned 6.
Sorry I can't be more help, that is all I can think of and are my opinions only - I don't have any experience of the US school system (except what I have read on this forum).
I think that it is wonderful that you are thinking ahead for your son.
